Data di Pubblicazione:
2023
Citazione:
Monotonicity in undirected networks / P. Boldi, F. Furia, S. Vigna. - In: NETWORK SCIENCE. - ISSN 2050-1242. - 11:3(2023 Sep), pp. 351-373. [10.1017/NWS.2022.42]
Abstract:
Is it always beneficial to create a new relationship (have a new follower/friend) in a social network? This
question can be formally stated as a property of the centrality measure that defines the importance of the
actors of the network. Score monotonicity means that adding an arc increases the centrality score of the
target of the arc; rank monotonicity means that adding an arc improves the importance of the target of the
arc relatively to the remaining nodes. It is known that most centralities are both score and rank monotone
on directed, strongly connected graphs. In this paper, we study the problem of score and rank monotonicity
for classical centrality measures in the case of undirected networks: in this case, we require that score, or
relative importance, improve at both endpoints of the new edge. We show that, surprisingly, the situation
in the undirected case is very different, and in particular that closeness, harmonic centrality, betweenness,
eigenvector centrality, Seeley’s index, Katz’s index, and PageRank are not rank monotone; betweenness
and PageRank are not even score monotone. In other words, while it is always a good thing to get a new
follower, it is not always beneficial to get a new friend.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Centrality; score monotonicity; rank monotonicity
Elenco autori:
P. Boldi, F. Furia, S. Vigna
Link alla scheda completa:
Link al Full Text: