2.9 集聚系数

一个节点的度未包含该节点邻居之间关系的信息。这些邻居节点是彼此相连的还是相互孤立的？这个问题可以用局部集聚系数Ci来回答，Ci反映了节点i的直接邻居之间的链接密度：Ci=0意味着节点i的邻居之间没有链接，Ci=1则意味着节点i的任意两个邻居之间都相互连接（见1.10节）。

对于随机网络中的一个节点i，要计算其集聚系数Ci，我们需要估计出该节点的ki个邻居之间的链接数Li。随机网络中，节点i的两个邻居之间的链接概率是p。由于节点i的ki个邻居之间最多有ki(ki-1)/2条链接，Li的期望值为：

因此，随机网络的局部集聚系数为：

公式2.21给出了两个预测：

（1）给定的情况下，网络越大，节点的集聚系数越小。因此，节点的局部集聚系数和1/N成正比。注意，网络的平均集聚系数也服从公式2.21。

（2）随机网络中，节点的局部集聚系数和节点的度相互独立。

为了测试公式2.21的有效性，我们绘制了几个无向网络的/关于网络大小N的函数（图2-13a）。我们发现，/并非按照N-1的速度减少，而是与N大体上相互独立，这一点和公式2.21的第一个预测不符。图2-13b~d展示了三个真实网络中C对节点度ki的依赖性，我们发现C(k)随着节点度增加而下降，违背了公式2.21的第二个预测。

图2-13 真实网络的集聚系数

（a）真实网络的集聚系数和公式2.21预测的随机网络的集聚系数。圆圈及其颜色对应表2-2中的网络。为了计算和，我们将有向网络视为无向网络。绿色的线对应公式2.21预测的随机网络的集聚系数——按照N-1减少。与之相反，真实网络中，集聚系数似乎与N是相互独立的。

（b）~（d）局部集聚系数C(k)对（b）互联网、（c）科学合作网络、（d）蛋白质相互作用网络节点度的依赖性。C(k)是节点度为k的所有节点的平均局部集聚系数。绿色水平线对应的是。

总之，随机网络模型不能刻画真实网络的集聚特性。相反，在具有同样的N和L的情况下，真实网络的集聚系数比随机网络预测的集聚系数要高得多。瓦茨和斯托加茨对随机网络模型进行了扩展[29]，解决了高集聚系数和小世界性质共存的问题（边栏2.9）。然而，扩展后的随机网络模型仍然不能解释为什么大度节点的集聚系数比小度节点的集聚系数要小。第8章将探讨能够解释C(k)形状的模型。

边栏2.9

瓦茨－斯托加茨模型

邓肯·瓦茨和史蒂夫·斯托加茨对随机网络模型进行了扩展（图2-14），该扩展基于如下两个观察[29]：

图2-14 瓦茨－斯托加茨模型[29]

（a）首先从节点环开始，每个节点和它的直接邻居及二阶邻居相连。因此，初始时，每个节点有=3/4（p=0）。

（b）每条链接以概率p重连到一个随机选择的节点。当p较小时，网络仍然保持高聚集性，不过随机连接带来的“长程边”可以大大缩短节点间的距离。

（c）当p=1时，所有链接都进行了重连，网络变成了随机网络。

（d）平均路径长度d(p)和集聚系数对重连参数p的依赖性。注意，d(p)和〈C（p）〉已经分别使用d(0)和进行了归一化，这里的d(0)和是从最初的规则格子网络中得出的（图a所示的p=0的情况）。d(p)的快速下降标志着小世界现象的发生。在d(p)的下降过程中，仍然保持很高的数值。因此，在0.001＜p＜0.1的范围内，短网络路径长度和高聚集性共存。这里的所有图，都有N=1000和=10。

（1）小世界性质

真实网络中，两个节点之间的平均距离对网络大小N的依赖关系是对数形式（公式2.18），而不是规则格子网络中的多项式形式（图2-11）。

（2）高集聚系数

真实网络的平均集聚系数远远高于具有类似N和L的随机网络（图2-13a）。

瓦茨－斯托加茨模型（也称小世界模型）介于规则格子网络和随机网络之间：规则格子网络具有高集聚系数，但没有小世界性质；随机网络具有小世界性质，但集聚系数低（图2-14a~c）。数值模拟表明，在链接重连参数的很大取值范围内，网络同时具有低平均路径长度和高集聚系数，从而重现了高集聚系数和小世界性质共存的现象（图2-14d）。

作为随机网络模型的一种扩展，瓦茨－斯托加茨模型预测，节点的度分布类似泊松分布。因此，像图2-6中展示的那样，网络中不存在大度节点。此外，瓦茨－斯托加茨模型预测，C(k)和k无关，无法刻画图2-13b~d中观察到的C(k)和k之间的相关性。我们在下一章中将会看到，要想理解小世界性质和高集聚系数共存的现象，必须首先能够正确刻画网络的度分布。