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.

Maria Castaldo

Researcher in Applied Mathematics and Computational Social Science

My research interests include opinion dynamics, social media and network analysis.