On a Centrality Maximization Game
(2020) In IFAC-PapersOnLine 53(2). p.2844-2849- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/972b8008-6d13-4733-98c9-858c8eb0f6d2
- author
- Castaldo, Maria ; Catalano, Costanza ; Como, Giacomo LU and Fagnani, Fabio
- organization
- publishing date
- 2020-01-01
- type
- Contribution to journal
- publication status
- published
- subject
- in
- IFAC-PapersOnLine
- volume
- 53
- issue
- 2
- pages
- 2844 - 2849
- publisher
- IFAC Secretariat
- external identifiers
-
- scopus:85105066014
- ISSN
- 2405-8963
- DOI
- 10.1016/j.ifacol.2020.12.954
- project
- Dynamics of Complex Socio-Technological Network Systems
- language
- English
- LU publication?
- yes
- id
- 972b8008-6d13-4733-98c9-858c8eb0f6d2
- alternative location
- https://linkinghub.elsevier.com/retrieve/pii/S2405896320313100
- date added to LUP
- 2022-02-14 17:32:37
- date last changed
- 2022-07-12 11:57:47
@article{972b8008-6d13-4733-98c9-858c8eb0f6d2,
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.}},
author = {{Castaldo, Maria and Catalano, Costanza and Como, Giacomo and Fagnani, Fabio}},
issn = {{2405-8963}},
language = {{eng}},
month = {{01}},
number = {{2}},
pages = {{2844--2849}},
publisher = {{IFAC Secretariat}},
series = {{IFAC-PapersOnLine}},
title = {{On a Centrality Maximization Game}},
url = {{http://dx.doi.org/10.1016/j.ifacol.2020.12.954}},
doi = {{10.1016/j.ifacol.2020.12.954}},
volume = {{53}},
year = {{2020}},
}