论文标题
无向网络中的单调性
Monotonicity in Undirected Networks
论文作者
论文摘要
在社交网络中建立新的关系（有一个新的追随者/朋友）总是有益的吗？这个问题可以正式表示为定义网络参与者重要性的中心度度量的属性。得分单调性意味着添加ARC会增加弧目标的中心度得分；等级单调性意味着添加ARC可以提高弧度相对与其余节点的重要性。众所周知，大多数核心既是定向，紧密连接的图表上的得分和排名单调。在本文中，我们研究了不向网络的情况下的分数和等级单调性问题：在这种情况下，我们需要分数或相对重要性在新优势的两个端点上有所改善。我们表明，令人惊讶的是，在无向案件中的情况是非常不同的，尤其是紧密的，谐波的中心性，中间，特征向量的中心性，Seeley的指数，Katz的索引和Pagerank不是单调的。介绍和Pagerank甚至都不是单调的。换句话说，虽然获得新的追随者总是一件好事，但结识新朋友并不总是有益的。
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.
