下载掌阅APP，畅读海量书库
立即打开
在介绍了随机网络模型后，本节将基于上述模型开展模拟实验，并对实验结果进行分析，进而描述随机网络的三大特性。
在Erdos和Renyi提出的随机网络中，任意两个节点之间连接一条边的概率为
p
（0≤
p
≤1）。因此，对于一个含有
N
个节点的随机网络，边的总数是一个期望值为
p
[
N
（
N
-1）/2]的随机变量，其平均度为〈
k
〉=
p
（
N
-1）。由此可以推出产生一个有
N
个节点和
M
条边的随机网络的概率为
。图2-5显示了不同连接概率下随机网络的示例。
图2-5 不同连接概率下的随机网络示例
含有
N
个节点的随机网络中，任意一个节点度为
k
的概率为
，可见随机网络中节点的度分布服从二项分布，其概率函数为
当网络的规模 N 很大且任意两点连接的概率 p 很小时，网络中节点的度分布可以用泊松分布来表示：
Erdos和Renyi系统性地研究了当 N →∞时，随机网络的性质与连接概率 p 之间的关系。在连接概率为 p 的随机网络中，当 N →∞时，生成的随机网络具有某种性质 Q 的概率为1，则称连接概率为 p 的随机网络具有性质 Q 。他们发现随机网络的很多性质都是突然涌现的。即连接概率小于某阈值时，该连接概率下的所有随机网络都不具有某性质，连接概率一旦大于某阈值时，该连接概率下的随机网络几乎都具有某性质。本书采用模拟生成随机网络的方式，直观地展示随机网络的性质。生成随机网络的伪代码如算法2-1所示。
算法2-1 生成随机网络伪代码
输入： 随机网络节点数 N ，节点之间的连接概率 p ；
输出： 随机网络 G
1.创建包含 N 个节点的图；
2.遍历图中两个节点的任意组合；
3.随机生成0～1之间的小数 n 。当 n ＜ p 时，连接两节点；
4.返回随机网络 G
根据上述伪代码，使用Python语言上提供的NetworkX工具包
，按不同概率生成的随机网络如图2-6所示。
图2-6 不同连接概率的10节点随机网络
可以很直观地看出，10个节点的网络，随机生成概率分别为0.1、0.5、0.8时，随机网络中的边随着连接概率的增加逐渐增多。当生成概率 p =0.1时，随机生成的网络中没有一个网络是一个整体，并且含有多个离散的点。而当 p =0.5时，随机生成的三个网络都是一个整体。当 p =0.8时，可以观察到网络中的边明显比生成概率为0.5时要多很多，近乎为全连通网络，具有较高地生成全连通网络的概率。当 p =1时，随机生成的网络永远为全连通网络。有了以上直接的观察过后，接下来具体地了解随机网络的三大特性。
随机网络的连通性是指在一个随机网络中，从一个节点出发可以到达任意一个节点，则称该随机网络具有连通性。这与逾渗理论 [8] 相仿，逾渗理论研究的是从网络最外围的一个节点进入，穿过网络到达距进入节点最远端的节点，形成可以渗透整个网络的通道出现的概率。把网络节点间的通道作为两个节点连接的形式，那么一个网络是连通的等价于这个网络是可以渗透的。举一个例子，当大量的纽扣（ N ≫1）散落在地上，每两个纽扣之间相同的概率 p 系上一条线，于是得到一个有 N 个点，约有 p [ N （ N -1）/2]条边的随机网络。如果捡起一颗纽扣，有概率通过连线直接捡起整个网络。模拟实验结果显示，如果概率 p 大于某个临界值 p c ∝（ln N ）/ N ，那么几乎每一个随机网络都是连通的，也就是说随机捡起任意一颗纽扣，都会连带捡起地上几乎所有的纽扣。
在一个包含10个节点的网络中，根据式（ln N ）/ N ，则阈值假设为（ln10）/10≈0.23。分别模拟十万次和一百万次生成概率为0.1、0.2与0.25的随机网络，统计网络中最大的连通网络。算法2-2显示了连通性实验伪代码。
算法2-2 连通性实验伪代码
输入： 随机网络节点数 N =10，节点之间的连接概率 p 1 =0.25， p 2 =0.2， p 3 =0.1，模拟生成次数num 1 =100000，num 2 =1000000；
输出：
平均最大连通网络节点数
，
，
，
，
，
，其中上标对应于两种不同的次数
n
1
，
n
2
，下标对应于节点之间的连接概率
p
1
，
p
2
，
p
3
；
1.创建包含 N 个节点的图；
2.遍历图中两个节点的任意组合；
3.随机生成0～1之间的小数 n ，当 n ＜ p 时，连接两节点；
4.得到随机网络 G ；
5.计算随机网络 G 中最大连通网络的节点个数 gˈ ；
6.重复生成num次，计算最大连通网络的节点个数的平均值 g ；
7.分别取 p 值为 p 1 ， p 2 ， p 3 ，取num值为num 1 ，num 2 ，重复进行步骤（1）～（6）；
8.返回平均最大连通网络节点数
，
，
，
，
，
从表2-5可以发现，当 p =0.25时，平均最大连通网络中的节点十分接近节点总数，也就意味着通过一颗纽扣几乎能拉起的纽扣，通过模拟得到能拉起的纽扣总数的期望约为9.94。生成概率为0.2时，因为生成概率与阈值差距不大，通过模拟得到能拉起的纽扣总数的期望约为9.78，也接近于1。当选择生成概率为0.1时，通过模拟得到能拉起的纽扣总数的期望约为7.49。随着模拟次数增大，因为受到每次模拟随机性的影响，所得期望减少是可以接受的。但可以确定的是，随着模拟次数增多，模拟结果更接近真实的期望值。由于理论证明的结果是在节点数量趋于无穷的情况下，几乎每一个随机网络都是连通的。受到收敛速度与“几乎”的限制，在模拟过程中不可能到达真实的极限结果，只能尽可能接近，因此结果似乎不如想象中理想，但是仍然能看出生成概率在超过阈值之后，网络全连通的概率更接近于1。
表2-5 连通性实验中随机网络的平均最大连通网络
随机网络的平均度是〈 k 〉= p （ N -1）≈ pN 。设 L 是随机网络的平均路径长度。若在随机网络中随机选取一个点，网络中会约有〈 k 〉 L 个其他的点与该点之间的距离等于或者非常接近于 L 。因此 N ∝〈 k 〉 L ，即 L ∝ln N /ln〈 k 〉≈ln N /ln pN =ln N /（ln p +ln N ）。这说明即使随机网络的规模非常庞大，其平均路径长度也可以相对较小，这反映了随机网络具有小世界性（具体参考第3章）。接下来通过模拟生成随机网络，验证上述理论观点。分别模拟生成概率为0.5，具有20、200与500个节点的网络，统计它们的平均路径长度，其中设定边的距离均为1。算法2-3显示了小世界性实验伪代码。
算法2-3 小世界性实验伪代码
输入： 随机网络节点数 N 1 =20， N 2 =200， N 3 =500，节点之间的连接概率 p =0.5；
输出： 平均最短路径 L 1 ， L 2 ， L 3 ；
1.创建包含 N 个节点的图；
2.遍历图中两个节点的任意组合；
3.随机生成0～1之间的小数 n 。当 n ＜ p 时，连接两节点；
4.得到随机网络 G ；
5.计算随机网络 G 中平均最短路径 L ；
6.分别取 N 值为 N 1 ， N 2 ， N 3 ，重复进行步骤（1）～（5）；
7.返回平均最大连通网络节点数 L 1 ， L 2 ， L 3
从表2-6的结果可以看出，随着网络节点数的增大，网络的平均最短路径在缓慢下降。由式子 L ∝ln N /（ln p +ln N ）可以看出，随着网络规模的扩大，平均最短路径会逐渐减小，并趋近于1。最终当平均最短路径接近1时，对应网络的规模由随机网络的连接概率 p 决定。当 p =1时， L =1。当 p ＜1时，随着网络规模 N 的增大 L →1，并且 p 越小，想要 L 趋近于1所需的 N 值相对越大。
表2-6 小世界性实验中随机网络的平均最短路径
不聚类性由聚类系数反应，聚类系数是表示网络中节点聚集程度的系数，它源于社会学中的“可传递三元组比率”。聚类系数描述了网络中个体的邻居节点也互为邻居的可能性。节点 i 的聚类系数 C i 定义为
其中 i ≠ j ≠ k 。 a i，j 表示网络中节点 i 和 j 之间的连边，若存在连边则 a i，j =1，否则 a i，j =0。一种更直观的理解，对于节点 i ，其邻居节点个数为 n ，其所有邻居节点可能构成的边数为 n （ n -1）/2，其所有邻居节点实际存在的边数为 e ，则计算节点 i 的聚类系数为
因此整个网络的聚类系数为
其中， n 为网络中节点的总数。直观上理解网络聚类系数，是每个节点的聚类系数之和除以节点总数。
对于随机网络，单个节点的邻居节点个数为 np ，其所有邻居节点可能构成的边数为 np （ np -1）/2，其所有邻居节点实际存在的边数为可能构成的边数乘以连接概率 p 。所以在 np 个邻居节点所构成的子网络中，按连接概率 p 连接的边数， p × np （ np -1）/2。则单个节点聚类系数为
在随机网络中，整个网络的聚类系数为
在连接密度相对高的现实网络中，节点之间倾向于形成一个团体关系。因此现实网络中的聚类系数往往比随机网络的聚类系数更大。对一个连接概率为 p 的随机网络而言，其聚类系数为 C = p ，等于随机网络边的连接概率。
在具有聚类特性的复杂网络中，比如一个人的朋友圈，在其中任意找两个朋友，这两个朋友之间互为朋友的概率相对于任意两个陌生人互为朋友的概率更大。如果一个网络是完全随机的，那么一个人的两个朋友之间互为朋友的概率，就和任意两个陌生人互为朋友的概率是完全相同的，这是很小的概率。所以说现实中的复杂网络，它并不是完全随机的，而是具有比完全随机网络高得多的聚类特性，这也是人们通过对许多大型现实的复杂网络的数据统计分析得到的结论。在随机网络中，由于所有节点的连接概率都遵循同一个概率值，当随机网络保持网络中所存在的边的个数与复杂网络相同时，网络中的节点数也相等，聚类系数会明显小于复杂网络，因此体现为不聚类性。
接下来通过模拟生成随机网络，与一个现实中的复杂网络相对比验证不聚类性。这里选取了扎卡里空手道俱乐部图（Zachary's Karate Club Graph）为对照网络。扎卡里空手道俱乐部图 [9] 是社会网络分析领域中的经典数据集，社会学家Zachary用两年的时间来观察美国一所大学中的空手道俱乐部34名成员间的社会关系。基于这些成员在俱乐部内部及外部的交往情况，构造了成员之间的社会关系网。其节点数目为34，连边数为78。选取一个节点总数为34，按0.1的连接概率生成一个具有和扎卡里网络一样节点的随机网络，并保证连接边数与扎卡里网络相近。然后分别计算扎卡里网络与生成的随机网络的聚类系数，进行对比。算法2-4显示了不聚类性实验伪代码。
算法2-4 不聚类性实验伪代码
输入： 随机网络节点数 N =34，节点之间的连接概率 p =0.1；
输出： 聚类系数 C ；
1.创建包含 N 个节点的图；
2.遍历图中两个节点的任意组合；
3.随机生成0～1之间的小数 n 。当 n ＜ p 时，连接两节点；
4.得到随机网络 G ；
5.计算随机网络 G 的聚类系数 C ；
6.返回聚类系数 C
重复进行了5次模拟实验，从表2-7的结果可以看出，生成的随机网络具有比扎卡里网络更多的连边数，但是聚类系数却与扎卡里网络的聚类系数相差巨大。读者可以尝试更小的边的连接概率，将生成的随机网络的连变数与扎卡里网络更加贴近，再观察聚类系数的变化。可以预见在连接概率更小的情况中，聚类系数将变得更小，验证了随机网络的不聚类性，间接说明了在现实中复杂网络的聚类特性。
表2-7 不聚类性实验中的连边数与聚类系数
读者可以尝试运行本书提供的代码，更进一步体会感受随机网络的生成、连通性、小世界性和不聚类性。