On a Centrality Maximization Game
| Autor: | Fabio Fagnani, Giacomo Como, Maria Castaldo, Costanza Catalano |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
PageRank
game theory FOS: Computer and information sciences social networks Computer Science::Computer Science and Game Theory 0209 industrial biotechnology Computer science Systems and Control (eess.SY) 02 engineering and technology Electrical Engineering and Systems Science - Systems and Control law.invention Combinatorics symbols.namesake 020901 industrial engineering & automation 91A06 91A43 60J20 law Network centrality network formation Bonacich centrality PageRank game theory social networks FOS: Electrical engineering electronic engineering information engineering FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Bonacich centrality Network centrality Social and Information Networks (cs.SI) Node (networking) Probability (math.PR) 020208 electrical & electronic engineering Computer Science - Social and Information Networks Core (game theory) Control and Systems Engineering Nash equilibrium Best response symbols Graph (abstract data type) Centrality Game theory network formation Mathematics - Probability |
| Zdroj: | IFAC-PapersOnLine. 53:2844-2849 |
| ISSN: | 2405-8963 |
| DOI: | 10.1016/j.ifacol.2020.12.954 |
| Popis: | 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. Comment: 10 pages, 11 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|