Spectral centrality measures keep rank when edges added in networks
Semi-Monotonicity for Spectral Centrality Measures
Social and Information Networks
Summary
When you add a connection between two points in a network, the way their importance scores change is not always predictable, especially in undirected networks. The authors study spectral centrality measures—ways to assign importance based on connections—and show that for three common ones, at least one of the connected points will not lose importance, and usually their scores do not drop either. This means adding a link can’t decrease the PageRank or similar scores of both endpoints in undirected networks, answering a question from earlier studies. The results help clarify how these centrality scores behave as networks grow.
What this means in practice
- •For network analysts: Improve reliability of importance scores when updating undirected network structures by knowing at least one endpoint's rank won't decrease after adding edges.
- •For web infrastructure teams: Ensure PageRank scores remain stable for at least one linked endpoint when modifying link structures in undirected scenarios.
A theory result. No direct application yet.
Authors
Paolo Boldi, Davide D'Ascenzo, Flavio Furia, Sebastiano Vigna
Abstract
Score monotonicity and rank monotonicity are properties describing the behavior of a centrality measure when an arc is added to a network: the former requires that the score of the target of the arc should increase, the latter that its importance with respect to the remaining nodes should not deteriorate. While in directed networks almost all classical centrality measures satisfy both properties, in undirected networks they fail for most measures: adding an edge can reduce the score or the rank of one of its endpoints. Semi-monotonicity is a recently introduced weaker property for undirected networks, requiring that at least one of the two endpoints of the new edge enjoys monotonicity, and it is known to hold for closeness, harmonic centrality, distance-decay centralities and betweenness. In this paper we study semi-monotonicity for three classical spectral centrality measures: eigenvector centrality, Katz's index, and PageRank. We prove that all of them are strictly rank semi-monotone on connected undirected graphs, and that all of them are also score semi-monotone, (the only exception being eigenvector centrality when scores are normalized by projecting the constant vector on the dominant eigenspace, for which we provide a counterexample). In particular, adding an edge can never decrease the PageRank of both its endpoints, which answers a question left open in previous work.