中心性悖论：为什么你的朋友总是更重要-计算机科学-机器学习-算法.pdfVIP

中心性悖论：为什么你的朋友总是更重要

RAJATSUBHRAHAZRAANDEVGENYVERBITSKIY

摘要.我们重新审视经典的朋友悖论，该悖论表明平均而言一个人的朋友至少拥有与自己一样多的朋

友，并将其推广到各种网络中心性度量。特别地，我们证明对于任何不可约的无向图，“朋友-平均”

程度、特征向量中心性、路径计数、Katz和PageRank中心性的值超过全局平均值。我们证明该结果

来自于与Perron特征值对应的特征向量的变分特征。

1.介绍

本友谊悖论首次由Feld(1991)提出，它表明平均而言，你的朋友比你有更多的朋友。尽管被视

译为悖论，但这在任何具有最少假设的一般图上都可以很容易地被证实为事实。这一现象源于采样

中偏差，即高度节点在当地邻域中出现的频率更高，增加了典型个体所看到的平均度数。这个悖论不

仅仅是奇闻异事，它影响我们对网络中的流行性、影响力和规范的认知，并在诸如疾病或错误信息

1

v传播等现象中发挥作用。最近有很多工作探讨了友谊悖论对认知的影响，参见例如Cantwelletal.

9(2021),EomandJo(2014),Hodasetal.(2013),Kumaretal.(2024),Wilson(2010)。

5

0友谊悖论断言，在任意有限、无向连通图中，

3

1.

7

0

5其中表示节点的度数，而表示相邻。等价地说，如果随机选择一个节点，然后从其邻居

2

:中随机挑选一个，那么该邻居的度数在统计上至少与一样大。证明这一结果的方法有多种。

v

i图中节点的度本身就是一种中心性度量。中心性度量为网络中的每个节点分配一个数值分数，

x

r以捕捉其相对重要性；常见的例子包括度中心性、PageRank、特征向量中心性、Katz中心性和介数

a

中心性，每种都强调了节点影响力的某个不同方面。因此，将友谊悖论推广到“中心性悖论”是很自

然的，该悖论指出，在平均意义上，你的朋友比你更具有中心性。近年来，已经提出了这样的推广。

例如，Higham(2019)分析了一个版本的中心性悖论，在这个版本中，选择一条随机边（友谊），然

后选择这条边上一个随机端点，并将采样朋友的平均中心性与全局平均值进行比较。Cantwelletal.

(2021)表明，如果你用每个节点上的任何非负属性替换“度”，那么随机采样的邻居中的平

均值与全局平均值之间的差异受和度之间的协方差支配。换句话说，你的朋友在属性上看起

来是否比普通人“更大”，完全取决于与度数的相关性有多强。

在本文中，我们采取了一个互补的角度：不是抽样一条边及其一个端点，而是通过平均每个

节点的邻居中心性来重新表述这个悖论。对于这种中心性度量，我们将每个的

平均值与总体的平均值进行比较。通过这种“邻居平均”的定义，我们证明了

由此产生的中心性悖论不仅适用于度数，还适用于特征向量中心性、行走计数中心性（邻接矩阵的

幂）、Katz中心性和强连通有向图上的PageRank。

Date:2025年7月19日.