论文标题
在无向网络上的光谱等级单调性
Spectral Rank Monotonicity on Undirected Networks
论文作者
论文摘要
我们研究光谱排名方法（例如特征向量中心性和Pagerank）的分数和等级单调性问题，在非方向网络的情况下。得分单调性意味着增加边缘在边缘的两端增加得分。等级单调性意味着添加边缘可以改善边缘两端相对于其余节点的相对位置。众所周知，在定向，紧密连接的图上，常见的光谱排名既是得分和等级单调。我们表明，令人惊讶的是，对于无方向的图，情况却大不相同，尤其是Pagerank既不是得分也不是单调的。
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.
