On a Centrality Maximization Game
Abstract
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 Page Rank algorithm. In this paper we study a network formation game where each player corresponds to a node in the network to be formed. The action of a player consists in the assignment of m out-links and his utility is his own Bonacich centrality. We study the Nash equilibria (NE) and the best response dynamics of this game. In particular, 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.