友谊悖论随机图生成模拟检验

Table of Contents:

• 友谊悖论
• 理论证明
• 实验结果
• 实验心得

友谊悖论#

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

假设社交网络是一张无向图$G=( V,E)$，每个顶点是一个人，每条边表示两个端点上的人互为朋友。则对于任意一个人$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)$中，每个节点（人）度数（朋友数）的期望为：

$$\mathbf{E}_{\text{degree}} = \mu = \frac{2|E|}{|V|}$$

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

$$\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|}$$

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

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

所以有：

$$\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，删除$\frac{1}{2}n\times r\times p$条边，并随机生成新的边来代替。
3. 检验新生成得到的网络中，符合友谊悖论的点的数量，看是否超过半数。
4. 同一组参数反复生成多次网络，看符合友谊悖论节点超过半数的网络占比多少、符合友谊悖论节点的节点占比多少。
5. 更换参数多次实验，观察参数对友谊悖论效果的影响。

网络生成部分实现#

一般的初始化方式是直接将节点与前后$r/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

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

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/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.5$，$n$取$20,30,\cdots,100$，每组参数生成7张图取平均作为最终的节点占比。

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

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

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

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

初始度数r的影响#

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

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

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

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

更新概率p的影响#

固定$n=40, r=6$，$p$取$0,0.1,\cdots,1$，得到的悖论节点占比如下，整体呈随着随机性增大悖论占比增大的趋势：

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

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

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

生成网络随机性的影响#

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

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

实验心得#

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