Spectral Rank Monotonicity on Undirected Networks
This reveals a fundamental limitation in applying spectral rankings to undirected graphs, which is incremental but important for network analysis practitioners.
The paper tackles the problem of score and rank monotonicity for spectral ranking methods like PageRank on undirected networks, showing that, unlike in directed graphs, PageRank fails to be monotone in both aspects.
We study the problem of score and rank monotonicity for spectral ranking methods, such as eigenvector centrality and PageRank, in the case of undirected networks. Score monotonicity means that adding an edge increases the score at both ends of the edge. Rank monotonicity means that adding an edge improves the relative position of both ends of the edge with respect to the remaining nodes. It is known that common spectral rankings are both score and rank monotone on directed, strongly connected graphs. We show that, surprisingly, the situation is very different for undirected graphs, and in particular that PageRank is neither score nor rank monotone.