生物医学网络科学Biomedical Network Science
网络鲁棒性、渗流与级联失效14 / 17

数学推导与算法

阅读
约 2 分钟

本页补充正文中略去的推导与算法。随机失效阈值的“二项稀释”推导与 Newman–Ziff 基本算法见网络可控性与稳定性的数学推导；SIR 与边渗流的映射见网络上的传播与免疫的数学推导。

A. 生成函数解的阈值与临界指数（ER 网络）

由 P∞=ϕ(1−e−⟨k⟩P∞)P_\infty=\phi(1-e^{-\langle k\rangle P_\infty})，在 P∞P_\infty 小时展开 1−e−x≈x−x2/21-e^{-x}\approx x-x^2/2： P∞≈ϕ⟨k⟩P∞−12ϕ⟨k⟩2P∞2⇒P∞≈2(ϕ⟨k⟩−1)ϕ⟨k⟩2∝(ϕ−ϕc)1,P_\infty\approx\phi\langle k\rangle P_\infty-\tfrac12\phi\langle k\rangle^2P_\infty^2 \;\Rightarrow\;P_\infty\approx\frac{2(\phi\langle k\rangle-1)}{\phi\langle k\rangle^2}\propto(\phi-\phi_c)^1, 即 βp=1\beta_p=1，ϕc=1/⟨k⟩\phi_c=1/\langle k\rangle。对 ⟨k2⟩\langle k^2\rangle 发散的分布，G1(u)G_1(u) 在 u=1u=1 附近的展开含非整数次幂项，导致 βp\beta_p 依赖于 γ\gamma（Cohen 等 2002）。

B. 攻击阈值的推导要点

  1. 删除比例 ff 的最高度节点后，新的最大度由 f=∫kmax⁡′kmaxP(k)dkf=\int_{k'_{\max}}^{k_{\max}}P(k)\,dk 决定，忽略 kmaxk_{\max} 项得 kmax⁡′=kminf1/(1−γ)k'_{\max}=k_{\min}f^{1/(1-\gamma)}。
  2. 被删枢纽带走的边占全部边端的比例 f̃=1⟨k⟩∫kmax⁡′kmaxkP(k)dk=f(2−γ)/(1−γ)\tilde f=\frac{1}{\langle k\rangle}\int_{k'_{\max}}^{k_{\max}}kP(k)\,dk=f^{(2-\gamma)/(1-\gamma)}（用 ⟨k⟩≈γ−1γ−2kmin\langle k\rangle\approx\frac{\gamma-1}{\gamma-2}k_{\min}）。
  3. 无度相关时，这些边的另一端是随机的，剩余网络等价于“度分布截断于 kmax⁡′k'_{\max}、再随机删去比例 f̃\tilde f 的边”的网络。随机删边后 κ′=(1−f̃)κ+f̃\kappa'=(1-\tilde f)\kappa+\tilde f，代入 Molloy–Reed 条件 κ′=2\kappa'=2 得 (1−f̃)(κ−1)=1(1-\tilde f)(\kappa-1)=1，即 f̃=1−1/(κ−1)\tilde f=1-1/(\kappa-1)。
  4. 用截断幂律的 κ=2−γ3−γk′max⁡3−γ−kmin⁡3−γk′max⁡2−γ−kmin⁡2−γ\kappa=\frac{2-\gamma}{3-\gamma}\,\frac{k'^{\,3-\gamma}_{\max}-k_{\min}^{3-\gamma}}{k'^{\,2-\gamma}_{\max}-k_{\min}^{2-\gamma}}，代入 kmax⁡′k'_{\max} 与 f̃\tilde f，整理即得正文中的攻击阈值方程。

C. 自适应攻击的计算

算法 1  自适应度攻击（RD）与 R 指标
输入：图 G(V,E)，|V| = N
1. 用桶（按度分组的链表）存储节点；s ← [ ]
2. for Q = 1 … N:
3.     取出当前度最大的节点 v，删除 v
4.     对 v 的每个邻居 w：把 w 从度为 d 的桶移到度为 d−1 的桶
5.     计算最大连通分支 s(Q)/N
6. R ← (1/N) Σ s(Q)

第 3–4 步每次 O(kv)O(k_v)，总计 O(L)O(L)。第 5 步若每步重新做 BFS 是 O(N(N+L))O(N(N+L))；更快的做法是记录完整的删除顺序，然后逆序加回节点，用并查集维护最大分支（与 Newman–Ziff 相同），总复杂度近似 O(Lα(N))O(L\,\alpha(N))。介数攻击（RB）每步都需重算介数（Brandes 算法 O(NL)O(NL)），代价高，常用分批重算或抽样近似介数。

D. Motter–Lai 级联

算法 2  负载重分配级联
输入：G，容忍参数 α，触发节点 t
1. L ← 介数(G)；对每个 i：C_i ← (1+α) L_i
2. 删除 t
3. repeat
4.     L ← 介数(当前图)
5.     F ← { i : L_i > C_i }
6.     删除 F
7. until F 为空
8. return G = 最大分支节点数 / N

每轮重算介数 O(NL)O(NL)，轮数通常很少；大网络可用抽样介数近似。注意结论对“负载”的定义（最短路径、加权流、电力潮流）敏感。

E. Watts 级联条件

令 vv 为“沿一条随机边到达的节点属于易损团簇”的生成函数意义下的量。在局部树状网络中，从一个易损节点出发沿边扩散，到达节点的剩余度分布为 kP(k)/⟨k⟩kP(k)/\langle k\rangle，它是易损节点的概率为 ρk\rho_k。易损团簇的平均后代数为 m=∑kkP(k)⟨k⟩ρk(k−1),m=\sum_k\frac{kP(k)}{\langle k\rangle}\rho_k(k-1), 全局级联要求 m>1m>1，即 ∑kk(k−1)ρkP(k)>⟨k⟩\sum_kk(k-1)\rho_kP(k)>\langle k\rangle。这与 Molloy–Reed 判据形式相同，只是把度为 kk 的节点以概率 ρk\rho_k“占据”——级联问题被化归为以度相关占据概率的点渗流（Callaway 等 2000 处理过这类“依赖度的占据概率”）。

F. 相互依存网络的切点条件

记 h(μ)=p(1−e−⟨k⟩μ)2h(\mu)=p(1-e^{-\langle k\rangle\mu})^2，稳态 μ=h(μ)\mu=h(\mu)。pp 减小时，曲线 hh 下移；临界点是 hh 与对角线相切之时：μ=h(μ)\mu=h(\mu) 且 h′(μ)=1h'(\mu)=1。令 z=⟨k⟩μz=\langle k\rangle\mu，第一式给出 ⟨k⟩p=z/(1−e−z)2\langle k\rangle p=z/(1-e^{-z})^2，第二式等价于对 zz 求该表达式的极小值，数值上 zc≈1.2564z_c\approx1.2564，⟨k⟩pc≈2.4554\langle k\rangle p_c\approx2.4554。因为切点处 μc=zc/⟨k⟩>0\mu_c=z_c/\langle k\rangle>0，序参量在临界点不连续——这就是一级相变的来源。单一网络中 h(μ)=p(1−e−⟨k⟩μ)h(\mu)=p(1-e^{-\langle k\rangle\mu}) 在 μ=0\mu=0 处斜率为 p⟨k⟩p\langle k\rangle，相切发生在原点，相变连续。

继续阅读