Centrality Maximization Game

Whether we are aware of it or not, in our daily life we are surrounded by networks through which we interact and whose structure is modified by our actions or decisions. Our friendships and relationships are part of a bigger network in which people influence each others' opinions, the roads we travel every day are part of a wider traffic network, the web-pages we consult form part of the World Wide Web (WWW), our social media profiles are immersed in a broader structure where contents are shared. Moreover, by meeting a new person, by adding a new hyperlink in our website, by commenting or liking a post on someone else Facebook page, we actively contribute to form and modify the shape of the network. For these reasons, in the last decades, an increasing interest has been paid to measures which state the importance of certain node positions in a network. Such measures are called centrality measures and can describe, for instance, how much visible is a web page on the internet or how much influential is a person's opinion in a society. Definitions of centrality under this heading include the ones of P. Bonacich, L. Katz and the PageRank centrality, first defined by S. Brin and L. Page. In the light of the above considerations, strategies to increase a node's centrality are of non negligible importance. This work intends to address the question of how a node should choose to direct its out-link in order to maximise its PageRank centrality. Moreover, it investigates the structure the network acquires when every node tries to maximise its own PageRank centrality, in what will be defined as a Centrality Maximization Game, and it examines Nash equilibria and best responses dynamics of such a game under different constraints. Such an object of study can be ascribed to the category of Network Formation Dynamics and more precisely to the class of Network Formation Games, in the wake of Jackson and Wolinsky and Jackson and Watts researches. The researches carried out by this thesis have brought forth four major results. First of all, it has been proved that, in a Centrality Maximisation Game where every node is forced to have a unique out-link, Nash equilibria are all and only the structures with c>0 couples of nodes connected by an undirected link, and all the nodes not forming a couple pointing at nodes in couples. Furthermore, it has been showed that such a game is ordinal potential and therefore its best response dynamics is always converging to Nash equilibria. Moreover, when considering a Centrality Maximization Game where every node is forced to have exactly two out-links, we prove that the nodes towards which a generic node s should direct its out links have to be searched among the ones with distance smaller or equal to 2 from s. This result expresses the fact that the best strategy for every node s to maximise its global PageRank centrality, is to act locally, in a in-neighbourhood of radius 2 of s. In addition to this result, we show that strict Nash equilibria for such a game are all and only undirected graphs. We may emphasise that the result obtained in in the case of 1 or 2 out-links are often easily generalisable to the case in which every node has a generic number m of out-links. In the conclusions we therefore present some ideas on how to extend the achieved findings to generic Centrality Maximization Games.