渗流理论与网络碎裂

从格点渗流到网络

渗流（percolation）研究随机占据的元素何时连成贯穿整个系统的团簇。经典问题是：在二维正方格点上以概率 $p$ 放置“石子”，相邻石子相连，最大团簇有多大？渗流理论的核心结论是：团簇规模并不随 $p$ 平滑变化，而是在临界值 $p_c$ 处发生相变——低于 $p_c$ 只有许多小团簇，高于 $p_c$ 出现一个占有限比例的“渗流团簇”。二维正方格点的点渗流 $p_c\approx0.593$，三角格点为 $1/2$，简单立方格点约为 $0.3116$。

网络在随机失效下的碎裂正是“反向”的渗流：从完整网络开始，逐步随机删除比例 $f$ 的节点。$f<f_c$ 时巨分支仍在，$f>f_c$ 时网络碎成许多小块。

临界行为与普适性

在临界点附近，三个量服从幂律：

$$\langle s\rangle\sim|\phi-\phi_c|^{-\gamma_p},\qquad P_\infty\sim(\phi-\phi_c)^{\beta_p},\qquad \xi\sim|\phi-\phi_c|^{-\nu},$$

其中 $\langle s\rangle$ 是有限团簇（不含巨分支）的平均大小，$\xi$ 是关联长度。$\phi_c$ 依赖于格点类型，临界指数却只依赖于维数，这称为普适性：二维时 $\gamma_p=43/18$、$\beta_p=5/36$、$\nu=4/3$；维数 $d>6$ 时取平均场值 $\gamma_p=1$、$\beta_p=1$、$\nu=1/2$。没有空间嵌入、局部呈树状的随机网络相当于“无穷维”，因此 ER 网络的随机失效属于平均场普适类。度分布很宽的网络会偏离平均场：对 $P(k)\sim k^{-\gamma}$，Cohen 等（2002，Physical Review E）得到

$$\beta_p=\begin{cases}1/(3-\gamma),&2<\gamma<3\\ 1/(\gamma-3),&3<\gamma<4\\ 1,&\gamma>4\end{cases}$$

即只有 $\gamma>4$ 时才回到 ER 网络的行为。

有限网络中如何判定 $f_c$

真实网络是有限的，“$P_\infty$ 恰好为零”的点并不存在。常用的经验做法有三种：（1）1% 规则：最大分支首次降到原规模 1% 以下的 $f$（Barabási《Network Science》第 8 章对真实网络就采用此法）；（2）第二大分支峰值：第二大连通分支的规模（或有限团簇平均大小 $\langle s\rangle$）在临界点附近达到峰值，这是最符合渗流理论的定义；（3）对多个规模 $N$ 做有限尺度标度分析。不同规则给出的 $f_c$ 可以相差不少，报告时要写明。