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.

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]

Monotonicity in undirected networks

P. Boldi
Primo
;
F. Furia
Secondo
;
S. Vigna
Ultimo
2023

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.
Centrality; score monotonicity; rank monotonicity
Settore INF/01 - Informatica
   Fine-Grained Analysis of Software Ecosystems as Networks (FASTEN)
   FASTEN
   EUROPEAN COMMISSION
   H2020
   825328
set-2023
2-feb-2023
Article (author)
File in questo prodotto:
File Dimensione Formato  
monotonicity-in-undirected-networks.pdf

accesso aperto

Descrizione: Article, online first
Tipologia: Publisher's version/PDF
Dimensione 593.57 kB
Formato Adobe PDF
593.57 kB Adobe PDF Visualizza/Apri
monotonicity-in-undirected-networks.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 750.62 kB
Formato Adobe PDF
750.62 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/1023351
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact