Monotonicity in undirected networks
Bibliographic Data
| ID | 6161641 |
|---|---|
| Authors | Paolo Boldi (0000-0002-8297-6255, University of Milan), Flavio Furia (0009-0003-5265-4161, University of Milan), Sebastiano Vigna (0000-0002-3257-651X, University of Milan, corresponding author) |
| Year | 2023 |
| Volume | 11 |
| Issue | 3 |
| Pages | 351-373 |
| Publication date | 2023-02-02 |
| Peer Reviewed | Yes |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | Network Science (JOURNAL) |
| Journal identifiers | ISSN: 2050-1250 • E-ISSN: 2050-1242 |
| Publisher | Cambridge University Press (PUBLISHER • US) |
| DOI | 10.1017/nws.2022.42 |
| OpenAlex | W4319033145 |
| Language | EN |
| Citations received | 2 |
| References cited | 19 |
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, improves 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
Betweenness centrality · Centrality · Closeness · Combinatorics · Discrete mathematics · Monotone polygon · Monotonic function · PageRank · Rank (graph theory · Complex Network Analysis Techniques · Computer Science · Graph theory and applications · Mathematics · Opinion Dynamics and Social Influence · Theoretical Computer Science
| Unique citing works | 2 |
|---|---|
| Citations per year | 1 |
| Citation span | 2024 - 2024 (1) |
| Citation velocity | recent |
| Highly cited | No |
| Citation types | Neutral: 2 |