2019/11/15 by Castaldo, Maria, Catalano, Costanza, Como, Giacomo +1 · 1 citation
#60J20 #91A06 #91A43 #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Probability (math.PR) #Social and Information Networks (cs.SI) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · doi:10.48550/arxiv.1911.06737
The Bonacich centrality is a well-known measure of the relative importance of nodes in a network. This notion is, for example, at the core of Google's PageRank algorithm. In this paper we study a network formation game where each player corresponds to a node in the network to be formed and can decide how to rewire his m out-links aiming at maximizing his own Bonacich centrality, which is his utility function. We study the Nash equilibria (NE) and the best response dynamics of this game and we provide a complete classification of the set of NE when m=1 and a fairly complete classification of the NE when m=2. Our analysis shows that the centrality maximization performed by each node tends to create undirected and disconnected or loosely connected networks, namely 2-cliques for m=1 and rings or a special "Butterfly"-shaped graph when m=2. Our results build on locality property of the best response function in such game that we formalize and prove in the paper.