生成函数方法与 Molloy–Reed 判据

对“度分布给定、其余完全随机”的配置模型网络，渗流问题可以用生成函数精确求解（Callaway、Newman、Strogatz 与 Watts 2000，PRL；Newman、Strogatz 与 Watts 2001，PRE）。

两个生成函数

自洽方程

设 $u$ 为“沿一条随机边出发，不能通向巨分支”的概率。在点渗流中，这条边的另一端要么被删除（概率 $1-\phi$），要么保留且它的所有剩余边都不通向巨分支（概率 $\phi\,G_1(u)$）：

$$u=1-\phi+\phi\,G_1(u),\qquad P_\infty=\phi\,[1-G_0(u)].$$

边渗流只需把“节点被保留”换成“边被保留”：$u=1-\phi+\phi\,G_1(u)$，$P_\infty=1-G_0(u)$。两种渗流的 $u$ 方程相同，所以临界点相同，只是巨分支大小不同：点渗流多乘一个 $\phi$，因为删一个节点等于同时删掉它的全部边。$u=1$ 总是方程的解；非平凡解 $u<1$ 出现的条件是曲线 $1-\phi+\phi G_1(u)$ 在 $u=1$ 处的斜率大于 1，即

$$\phi\,G_1'(1)>1\iff\phi_c=\frac{1}{G_1'(1)}=\frac{\langle k\rangle}{\langle k^2\rangle-\langle k\rangle}.$$

完整网络（$\phi=1$）存在巨分支的条件 $G_1'(1)>1$ 等价于 $\langle k^2\rangle-2\langle k\rangle>0$，这就是 Molloy–Reed 判据（Molloy 与 Reed 1995）：$\kappa=\langle k^2\rangle/\langle k\rangle>2$。由 $\phi_c$ 立即得到随机失效阈值

$$f_c=1-\frac{1}{\kappa_0-1},\qquad\kappa_0=\frac{\langle k^2\rangle}{\langle k\rangle}.$$

这与结构鲁棒性中用“删点后度分布二项稀释”得到的结果一致，生成函数的好处是还能给出整条 $P_\infty(\phi)$ 曲线与团簇大小分布。临界点以下，含随机节点的团簇平均大小为

$$\langle s\rangle=\phi\left[1+\frac{\phi\,G_0'(1)}{1-\phi\,G_1'(1)}\right],$$

在 $\phi\to\phi_c$ 时发散。边渗流情形的推导与 SIR 最终规模的对应见网络上的传播与免疫的数学推导。

算例

算例 1（泊松网络）：ER 网络 $G_0(x)=G_1(x)=e^{\langle k\rangle(x-1)}$。由 $P_\infty=\phi[1-G_0(u)]$ 得 $G_0(u)=1-P_\infty/\phi$，代回 $u$ 的方程得 $u=1-P_\infty$，于是点渗流满足 $P_\infty=\phi\,(1-e^{-\langle k\rangle P_\infty})$，边渗流满足 $P_\infty=1-e^{-\phi\langle k\rangle P_\infty}$。取 $\langle k\rangle=4$：$\phi_c=1/4$，即要随机删掉 75% 的节点网络才碎裂；$\phi=0.5$ 时迭代得点渗流 $P_\infty\approx0.398$、边渗流 $P_\infty\approx0.797$。

算例 2（可手算的双值度分布）：一半节点度为 1、一半度为 3。$\langle k\rangle=2$，$\langle k^2\rangle=5$，$\kappa_0=2.5>2$，存在巨分支；$f_c=1-1/1.5=1/3$。完整网络中 $G_1(u)=(1\cdot\tfrac12+3\cdot\tfrac12u^2)/2=\tfrac14+\tfrac34u^2$，解 $u=\tfrac14+\tfrac34u^2$ 得 $u=1/3$，于是 $P_\infty=1-G_0(1/3)=1-(\tfrac12\cdot\tfrac13+\tfrac12\cdot\tfrac1{27})=44/54\approx0.81$。