Table of Contents:

友谊悖论#

友谊悖论指的是社交网络中,一个人的朋友数通常少于朋友的平均朋友数。从另一个角度来看,友谊悖论表明人们通常会与朋友和自己一样多或者更多的人交友。

假设社交网络是一张无向图G=(V,E)G=( V,E),每个顶点是一个人,每条边表示两个端点上的人互为朋友。则对于任意一个人vv,符合友谊悖论的情况用数学语言表示即:

d(v)vVd(v)1{v(v,v)E}(v)d(v)d(v) \le \frac{\sum_{v'\in V}d(v')\cdot \mathbf{1}_{ \{v'\mid (v,v')\in E \}}(v')}{d(v)}

理论证明#

在社交网络G=(V,E)G=( V,E)中,每个节点(人)度数(朋友数)的期望为:

Edegree=μ=2EV\mathbf{E}_{\text{degree}} = \mu = \frac{2|E|}{|V|}

每个节点被选为邻居的概率为d(v)E\frac{d(v)}{|E|},所以节点的邻居的度数均值的期望为:

Eneighbor=vd(v)(12d(v)E)=vd(v)22E\mathbf{E}_{\text{neighbor}} =\sum_{v}d(v)\cdot \left(\frac{1}{2}\cdot \frac{d(v)}{|E|}\right) = \frac{\sum_vd(v)^2}{2|E|}

由方差定义Var(X)=E[X2](E[X])2\operatorname{Var}(X)= \operatorname{E}\left[X^2 \right] - (\operatorname{E}[X])^2,度数的方差σ2\sigma^2满足:

σ2=vd(v)2Vμ2\sigma^2 = \frac{\sum_v d(v)^2}{|V|}-\mu^2

所以有:

Eneighbor=vd(v)22E=(σ2+μ2)V2E=μ+σ2μEdegree\mathbf{E}_{\text{neighbor}} =\frac{\sum_vd(v)^2}{2|E|} = \frac{(\sigma^2+\mu^2)|V|}{2|E|} = \mu + \frac{\sigma^2}{\mu} \ge \mathbf{E}_{\text{degree}}

因为方差为非负数,所以度数的期望小于邻居度数的期望。

###随机图生成算法

上文的理论证明对所有无向图都符合,下面通过代码实现来随机生成一些无向图,模拟检验在不同网络结构下,符合友谊悖论的节点占比。

基本算法思想#

  1. 生成节点数为n,每个节点度数为r的无向图网络。
  2. 根据给定的概率p,删除12n×r×p\frac{1}{2}n\times r\times p条边,并随机生成新的边来代替。
  3. 检验新生成得到的网络中,符合友谊悖论的点的数量,看是否超过半数。
  4. 同一组参数反复生成多次网络,看符合友谊悖论节点超过半数的网络占比多少、符合友谊悖论节点的节点占比多少。
  5. 更换参数多次实验,观察参数对友谊悖论效果的影响。

网络生成部分实现#

一般的初始化方式是直接将节点与前后r/2r/2个点相关联,然后依靠边的删除更新来增加随机性。

def initial_not_random(n, r):
global net
net = np.zeros([n, n])
for i in range(n):
for j in range(r):
jj = (i+j+1) % n
net[i][jj] = net[jj][i] = 1

实验时,还尝试了一种随机的初始化方式。即依次遍历nn个节点,每个节点随机选取朋友节点直到度数为rr。考虑到这种方法到后期可能因为无解需要回溯,这里设置了最大随机次数,超过随机次数则不再寻找朋友,因此这种初始化方式试图提高随机性,但节点度数不严格为rr,而是小于等于。

def initial_random(n, r):
global net
net = np.zeros([n, n])
max_trial = n
for i in range(n):
trial = 0
while np.sum(net[i] == 1) < r:
trial += 1
temp = np.sum(net[i] == 1)
j = random.randint(0, n - 1)
if j is not i and np.sum(net[j] == 1) < r:
net[i][j] = net[j][i] = 1
if (trial > max_trial):
break

随机扰动部分实现#

nr/2nr/2条边中的nrp/2\lfloor nrp/2\rfloor条依次删除并随机添加新边。

def adjust(num):
global net
for i in range(num):
edges = np.nonzero(net)
empty = np.nonzero(net == 0)
ran1 = random.randint(0, len(edges[0])-1)
ran2 = random.randint(0, len(empty[0])-1)
net[edges[0][ran1]][edges[1][ran1]] = net[edges[1][ran1]][edges[0][ran1]] = 0
net[empty[0][ran2]][empty[1][ran2]] = net[empty[1][ran2]][empty[0][ran2]] = 1

度数比较部分实现#

对所有的节点计算:1)度数向量;2)邻居度数均值向量。

def count_degree(n):
global net
cnt = []
cnt = [np.sum(net[i] == 1) for i in range(n)]
return cnt


def compare_degree(n, cnt):
global net
comp = []
for i in range(n):
neighbors = np.nonzero(net[i])
if len(neighbors[0]):
mean = np.mean(np.array(cnt)[neighbors[0]])
else:
mean = 0
comp.append(mean)
return comp

根据这两个向量的比较结果绘图,符合友谊悖论的点标记为黄色,不符合的标记为紫色,便于观察。

实验结果#

实验首先在非随机初始化的朴素生成算法上进行,观察了三个参数对友谊悖论的影响,其后观察参数固定时不同随机生成方法的差异。

节点数n的影响#

实验固定r=6,p=0.5r=6, p=0.5nn20,30,,10020,30,\cdots,100,每组参数生成7张图取平均作为最终的节点占比。

所有网络中,只有一张n=20n=20的网络只有9个节点符合友谊悖论,其余网络中符合友谊悖论的节点都超过半数。平均得到的符合悖论节点概率为:

image-20210322155607424

实验中观察到悖论节点的占比基本稳定在0.55~0.60左右,但可以观察到一个有趣的现象:

节点数小的网络在多次随机结果中,悖论节点概率变化较大:有出现不符合友谊悖论的网络,也出现过很多悖论节点概率达到0.6以上的结果。

image-20210322161456678

我认为这是由于节点度数的方差在节点数量较小时更不稳定,因此理论证明中两种度数期望的差异时小时大,从而导致悖论节点概率值也不稳定。

初始度数r的影响#

实验固定n=40,p=0.5n=40, p=0.5rr取6到40之间的数,得到的悖论占比概率如下:

image-20210322162427425

可以看到度数较低时,友谊悖论的概率还是稳定在0.55~0.60区间的。然而,当度数继续增大至超过总节点数的一半乃至3/4,符合友谊悖论的节点概率下降明显,甚至在r=34r=34时得到了0.5的结果。

笔者认为这是因为当度数过大时,几乎人人都与其他所有人有连接,最多也就达到度数为39,因而可能度数方差较小,期望的差异不大。

不过,在实际生活中,人数基数很大,通常不会出现认识半数以上的人的状况,所以符合社交网络的情况下,应当还是多数节点满足友谊悖论的。

更新概率p的影响#

固定n=40,r=6n=40, r=6pp0,0.1,,10,0.1,\cdots,1,得到的悖论节点占比如下,整体呈随着随机性增大悖论占比增大的趋势:

image-20210322163408043

p=0p=0时即有规律的初始化图像,如下图所示,显然没有符合友谊悖论的点:

n=40,r=6,p=0.0,id=5

稍稍增加随机性到p=0.1p=0.1,虽然友谊悖论的节点占比跃升至0.529,我们仍能从网络结构中看出类似环状的结构,这说明大部分人还是与周围临近的几个人交好,鲜少有横穿这个环到另一面交友的人:

n=40,r=6,p=0.1,id=5

到了p=0.9p=0.9时,已经完全看不出环形,而是聚成一团的实心球状网络:

n=40,r=6,p=0.9,id=2

生成网络随机性的影响#

实验之前以为随机生成的网络会提高友谊悖论的概率,事实证明似乎不会。实验中固定了n=40,r=6,p=0.2n=40, r=6, p=0.2,尝试每次生成100个网络取友谊悖论的节点占比均值,发现一般方法的概率为0.56875,随机方法的概率为0.5605。二者没有相差太多,甚至一般方法符合友谊悖论的概率更高。

这给了我一点启示,说明随机性和友谊悖论概率的关联不那么大,关键不在于生成的随机性,而在于节点度数的方差是不是够大。

实验心得#

  • 实验整体很有趣,虽然对python不是那么熟悉但是写起这个来还挺愉快的,可能因为和生活实际联系紧密。
  • 友谊悖论之所以叫悖论,是因为它违背了大部分人的自我认知,也就是说大多人会觉得是自己的朋友比较多,而不是朋友的朋友。但是如果换个角度考虑友谊悖论,就没有那么奇怪了,即:我们倾向于结交朋友多的人(这些人可能有有利于社交的性格、条件等)。
  • 从理论出发能够破除一些偏见,比如实验之前擅自认为原来的生成方式随机性不足,想要增加一些随机性。但事实是友谊悖论与随机性关联不大,而且实际的社交网络也并非随机生成的,而是符合一定的规律。
  • 进一步地做的话,可以考虑更切合实际地实现网络生成。比如给友谊边增加权重,或者进行一些聚类:给每个节点赋予一些“爱好”,让有相同爱好的人更有可能成为朋友等等。