2.6 随机网络的演化
本章开始时介绍的鸡尾酒会刻画了这样一个动态过程:从N个孤立节点开始,链接逐个放置在随机相遇的客人之间。这一过程等价于逐渐增加p的值,从而对网络拓扑结构产生影响(在线资源2.2)。为了量化这一过程,我们首先看一看网络中最大连通分支的大小NG是如何随着而变化的。两个容易理解的极端情形如下:
● 当p=0时,=0,所有节点都是孤立的。因此,最大连通分支的大小为NG=1。对于大的N,有NG/N→0。
● 当p=1时,=N-1,网络是完全连通图,所有节点属于同一个连通分支。因此,NG=N,NG/N=1。
在线资源2.2 随机网络的演化
该视频展示了随机网络的结构随着p的增加而变化的情况。从视频中可以形象地看出,当p很小时,网络中没有巨连通分支,而当p到达临界值时,一个巨连通分支突然就出现了。
扫描二维码下载“湛庐阅读”App,回复书名,观看随机网络的演化过程。
有人可能会认为,随着平均度从0增加到N-1,最大连通分支的大小是逐渐由NG=1变化到NG=N的。然而,如图2-7a所示,情况并非如此:当比较小时,NG/N一直为0,意味着没有大的连通分支出现;一旦超过临界值,NG/N开始迅速增加,标志着一个大的连通分支在快速形成,我们称该连通分支为巨连通分支。埃尔德什和雷尼在他们1959年发表的经典论文中预测了巨连通分支出现的条件[2]:
换句话说,当且仅当每个节点平均拥有不少于一个链接时,巨连通分支才会出现(进阶阅读2.C)。
每个节点至少需要一个链接才能使网络中出现巨连通分支,这一事实并不让人感到意外。实际上,巨连通分支的存在,要求其所包含的每个节点必须至少和一个该连通分支中的其他节点相连。巨连通分支的出现只需要每个节点拥有一个链接就足够了,这多少有点反直觉,但事实的确如此。
根据公式2.3,可以使用链接概率p来表示公式2.10:
因此,网络越大,形成巨连通分支所需要的p越小。
巨连通分支的出现,只是我们通过改变来刻画随机网络变化时观测到的其中一个转变。实际上,随着变化,我们可以观察到4个拓扑上有明显区别的状态(图2-7a),每个都有其独有的特性:
图2-7 随机网络的演化
(a)埃尔德什-雷尼随机网络模型中,巨连通分支的相对大小关于平均度的函数。从图中可以看出,该函数在=1处有一个相变,该相变标志着具有非零相对大小的巨连通分支出现了。
(b)~(e)示例随机网络及其在4种状态下的性质。
亚临界状态:
当=0时,网络由N个孤立节点构成。的增加意味着我们往网络中增加了N=pN(N-1)/2个链接。然而,由于<1,网络中只有少量的链接。因此在该状态下,网络中只有一些较小的连通分支(图2-7b)。
当然,任何时候我们都可以将最大连通分支指定为巨连通分支。然而,在这种状态下,最大连通分支的相对大小NG/N接近于0。原因是:当<1时,最大连通分支是一个大小为NG~lnN的树,最大连通分支大小的增加速度比网络大小的增加速度要慢得多。因此,在N→∞的极限情况下,NG/NlnN/N→0。
总之,亚临界状态下,网络由许多较小的连通分支组成,这些分支的大小服从指数分布(公式2.35)。因此,这些连通分支的大小相差不大,没有哪个连通分支的大小明显高于其他连通分支从而可以被指定为巨连通分支。
临界点:
临界点是网络从没有巨连通分支(<1)变化到有巨连通分支(>1)的边界。当网络处于临界点时,最大连通分支的相对大小仍然趋近于零(图2-7c)。实际上,此时最大连通分支的大小为NG~N2/3。因此,最大连通分支的大小NG比网络大小增长得慢得多,在N→∞的极限情况下,最大连通分支的相对大小NG/N~N-1/3→0。
不过,需要注意的是,最大连通分支的绝对大小在=1处有一个明显的跳跃。例如,对于有N=7×109个节点的随机网络——大小和全球社交网络相当,当<1时,最大连通分支的大小为NGlnN=ln(7×109)22.7。相比之下,当=1时,NG~N2/3=(7×109)2/33×106,比<1时提升了约5个数量级。然而,无论处于亚临界状态还是临界点,最大连通分支都只包含了网络所有节点中很小的一部分。
总之,在临界点,大多数节点出现在数量众多的小连通分支中,这些连通分支大小的分布服从公式2.36。幂律形式意味着,大小差异很大的连通分支并存。为数众多的小连通分支主要是树,而最大连通分支则可能包含环。注意,处于临界点状态的网络,其很多性质和处于相变状态的物理系统的性质相似(进阶阅读2.F)。
超临界状态:
这个状态最接近于真实系统,该状态下的最大连通分支开始像网络了。在临界点附近,最大连通分支大小的变化遵循:
或者:
这里的pc由公式2.11得到。换句话说,巨连通分支的相对大小不再是零。距离临界点越远,属于巨连通分支的节点所占的比例越大。注意,公式2.12只在=1附近有效。对于大的,NG和之间的依赖关系是非线性的(图2-7a)。
总之,在超临界状态下,许多孤立的小连通分支和一个巨连通分支并存,这些连通分支的大小服从分布(公式2.35)。这些小连通分支大多是树,而巨连通分支则由环或回路构成。超临界状态一直持续到所有节点都被巨连通分支吸收为止。
全连通状态:
当p足够大时,巨连通分支吸收了所有的节点,此时有NGN。由于没有孤立节点存在,整个网络变成连通的了。这种状态发生时,网络的平均度取决于N(进阶阅读2.E):
注意,在刚进入连通状态时,网络仍然是相对稀疏的。原因是:对于大的N,lnN / N→0。只有当=N-1时,网络才变成完全图。
总之,随机网络模型预测,网络的出现不是一个流畅的渐进过程:较小时观测到的孤立节点和小连通分支会经历一个相变,坍缩成一个巨连通分支(进阶阅读2.F)。通过改变,我们可以观测到4个拓扑结构不同的状态(图2-7)。
上述探讨采用的是一种实证的视角,该视角适用于将随机网络和真实系统进行对比。另外一种有着丰富内涵的视角来自数学文献(边栏2.5)。
边栏2.5
图论中的网络演化
在随机图论的文献中,人们往往假设链接概率p(N)正比于Nz,这里的z是介于-∞和0之间的一个可调参数[15]。埃尔德什和雷尼发现,调节z的值后,随机图的一些关键性质会突然出现。
如果一个图具有某种性质Q的概率在N→∞时接近于1,我们会说该图具有性质Q。也就是说,给定z的情况下,要么几乎所有的图都具有性质Q,要么几乎没有图具有性质Q。例如,当z小于-3/2时,几乎所有的图都只包含孤立节点和成对相连的点对。一旦z超过-3/2,大多数网络都含有连接3个或更多节点的路径(图2-8)。
图2-8 随机图的演化
在链接概率p(N)~Nz的随机图中,不同子图在随机图中出现的阈值概率。这里,阈值概率通过幂指数z来刻画。当z<-3/2时,图中只有孤立节点和边;当z的取值超过-3/2时,图中开始出现3阶树;当z<-4/3时,4阶树出现了;当z=-1时,各阶的树都出现了,同时出现的还有各阶的环;4阶完全图在z=-2/3时出现,并且随着z的取值进一步增加,更高阶数的完全图开始出现。[19]