生物医学网络科学Biomedical Network Science
网络结构指标与随机图13 / 19

ER 网络的演化与相变

阅读
约 2 分钟

设想从 NN 个孤立节点出发，不断随机加边（pp 从 0 增大）。直觉上最大分支应该平滑长大；实际上它在 ⟨k⟩=1\langle k\rangle=1 处突然“出现”。这是 Erdős 与 Rényi（1960）最著名的发现。

四个区间

区间 条件 最大分支规模 NGN_G 结构特征
亚临界 0<⟨k⟩<10<\langle k\rangle<1（p<1/Np<1/N） ∼ln⁡N\sim\ln N，NG/N→0N_G/N\to0 许多小分支，几乎都是树；平均分支大小 1/(1−⟨k⟩)1/(1-\langle k\rangle)
临界点 ⟨k⟩=1\langle k\rangle=1（p=1/Np=1/N） ∼N2/3\sim N^{2/3}，NG/N→0N_G/N\to0 分支大小分布为幂律 ps∼s−3/2p_s\sim s^{-3/2}，大小悬殊的分支共存
超临界 1<⟨k⟩<ln⁡N1<\langle k\rangle<\ln N ≈SN\approx SN，S=1−e−⟨k⟩SS=1-e^{-\langle k\rangle S} 一个含环的巨分支 + 许多树状小分支和孤立节点
连通区 ⟨k⟩>ln⁡N\langle k\rangle>\ln N（p>ln⁡N/Np>\ln N/N） =N=N 巨分支吸收所有节点，网络连通

几点说明：

  • 临界点 pc=1/Np_c=1/N 随规模增大而趋于 0：网络越大，越少的“边比例”就足以产生巨分支；但以平均度计，临界值总是 1，与 NN 无关。
  • 超临界区与连通区的分界 ln⁡N\ln N 随规模缓慢增长。以 N=7×109N=7\times10^9 的世界人口为例，ln⁡N≈22.7\ln N\approx22.7：只要每人平均认识二十几个人，一个随机社会就应该完全连通。
  • 连通的精确判据：令 p=(ln⁡N+c)/Np=(\ln N+c)/N，则网络连通的概率趋于 e−e−ce^{-e^{-c}}（Erdős 与 Rényi 1959）。原因是阻碍连通的最后障碍是孤立节点，其个数近似服从均值 Ne−⟨k⟩Ne^{-\langle k\rangle} 的泊松分布。代码示例在 N=2000N=2000 时验证了这一点：⟨k⟩=ln⁡N≈7.6\langle k\rangle=\ln N\approx7.6 时连通概率约 0.37，⟨k⟩=11\langle k\rangle=11 时约 0.97。

临界现象

巨分支的出现与水结冰、铁磁体在居里温度下出现磁化同属相变：一个序参量（这里是 SS）从 0 变为正值。在临界点附近，许多量呈幂律：

  • 序参量：⟨k⟩\langle k\rangle 略大于 1 时，把 1−e−⟨k⟩S1-e^{-\langle k\rangle S} 展开到 S2S^2 项得 S≈2(⟨k⟩−1)S\approx2(\langle k\rangle-1)，即 S∼(⟨k⟩−1)βS\sim(\langle k\rangle-1)^{\beta}，β=1\beta=1；
  • 平均分支大小（随机选一个节点，它所在小分支的大小）：⟨s⟩=1/[1−⟨k⟩+⟨k⟩S]\langle s\rangle=1/[1-\langle k\rangle+\langle k\rangle S]，亚临界时为 1/(1−⟨k⟩)1/(1-\langle k\rangle)，在 ⟨k⟩→1\langle k\rangle\to1 时发散，⟨s⟩∼|⟨k⟩−1|−γ\langle s\rangle\sim|\langle k\rangle-1|^{-\gamma}，γ=1\gamma=1；
  • 分支大小分布：随机选一个节点，它属于大小为 ss 的（非巨）分支的概率为 ps=e−⟨k⟩s(⟨k⟩s)s−1s!≈12πs−3/2e−(⟨k⟩−1)s+(s−1)ln⁡⟨k⟩.p_s=\frac{e^{-\langle k\rangle s}(\langle k\rangle s)^{s-1}}{s!}\;\approx\;\frac{1}{\sqrt{2\pi}}\,s^{-3/2}\,e^{-(\langle k\rangle-1)s+(s-1)\ln\langle k\rangle}. 偏离临界点时指数项使大分支被指数压制；在 ⟨k⟩=1\langle k\rangle=1 处指数项消失，ps∼s−3/2p_s\sim s^{-3/2}。

这些指数与 Bethe 晶格（无限维）上的渗流相同，称为平均场指数。巨分支相变与渗流理论是同一回事：随机删除节点或边相当于把平均度调低，网络在某个临界删除比例处碎裂（见网络鲁棒性、渗流与级联失效）。同样的阈值思想也出现在网络上的传播与免疫（传播阈值）中。

为什么是 1？沿一条边走到一个新节点，它平均还有多少条“向外”的边？对泊松度分布，剩余度均值为 ⟨k2⟩/⟨k⟩−1=⟨k⟩\langle k^2\rangle/\langle k\rangle-1=\langle k\rangle。若每一步平均找到的新节点少于 1 个，探索会像亚临界的分支过程一样很快灭绝；多于 1 个时有正概率无限延续，形成巨分支。一般度分布下的条件 ⟨k2⟩/⟨k⟩>2\langle k^2\rangle/\langle k\rangle>2 称为 Molloy–Reed 判据。

真实网络处在哪个区间？

Barabási 书表 3.1 列出了几个无向网络的 ⟨k⟩\langle k\rangle 与 ln⁡N\ln N：所有网络都有 ⟨k⟩>1\langle k\rangle>1，即都在超临界区之上；但多数网络的 ⟨k⟩<ln⁡N\langle k\rangle<\ln N，例如书中所用的酵母蛋白相互作用网络 N=2018N=2018、⟨k⟩=2.90\langle k\rangle=2.90、ln⁡N=7.61\ln N=7.61，只有演员合作网络（⟨k⟩=83.7\langle k\rangle=83.7，ln⁡N=13.5\ln N=13.5）处在连通区。按随机网络理论，这些网络应当碎裂成许多分支，并有不少孤立节点。互联网、电网事实上是连通的，这说明真实网络的连通性并非由随机连边决定。蛋白网络确实含有许多小分支，但这部分反映的是数据不完整，而不只是拓扑规律。

继续阅读