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

随机失效与无标度网络

阅读
约 2 分钟

二阶矩决定一切

fc=1−1/(κ0−1)f_c=1-1/(\kappa_0-1) 表明随机失效阈值只依赖 ⟨k⟩\langle k\rangle 和 ⟨k2⟩\langle k^2\rangle。对 ER 网络，⟨k2⟩=⟨k⟩(⟨k⟩+1)\langle k^2\rangle=\langle k\rangle(\langle k\rangle+1)，故 fcER=1−1/⟨k⟩f_c^{ER}=1-1/\langle k\rangle：总是有限，越稠密越耐删。对幂律分布 P(k)∼k−γP(k)\sim k^{-\gamma}（kmin≤k≤kmaxk_{\min}\le k\le k_{\max}），用连续度近似

κ=⟨k2⟩⟨k⟩≈|2−γ3−γ|×{kmin,γ>3kmax⁡3−γkmin⁡γ−2,2<γ<3kmax,1<γ<2\kappa=\frac{\langle k^2\rangle}{\langle k\rangle}\approx\left|\frac{2-\gamma}{3-\gamma}\right|\times \begin{cases}k_{\min}, &\gamma>3\\ k_{\max}^{3-\gamma}k_{\min}^{\gamma-2}, &2<\gamma<3\\ k_{\max}, &1<\gamma<2\end{cases}

  • γ>3\gamma>3：κ\kappa 有限，fcf_c 只由 γ\gamma 和 kmink_{\min} 决定，网络的行为与随机网络类似；
  • 2<γ<32<\gamma<3：kmax∼kminN1/(γ−1)k_{\max}\sim k_{\min}N^{1/(\gamma-1)} 随规模增大，κ→∞\kappa\to\infty，fc→1f_c\to1，即无限大的无标度网络必须删掉几乎全部节点才会碎裂（Cohen、Erez、ben-Avraham 与 Havlin 2000，PRL）。

有限网络中 fc≈1−CN−(3−γ)/(γ−1)f_c\approx1-C\,N^{-(3-\gamma)/(\gamma-1)}，网络越大越接近 1。直观原因：随机删除对度“视而不见”，而无标度网络中绝大多数节点是低度节点，删到枢纽的概率很小；只要枢纽还在，它们就把剩余节点连在一起。

增强鲁棒性：若一个网络的随机失效阈值高于同样 NN、LL 的随机网络，fc>fcERf_c>f_c^{ER}，称其具有增强鲁棒性。它不要求严格的幂律，只要求 ⟨k2⟩\langle k^2\rangle 明显大于 ⟨k⟩(⟨k⟩+1)\langle k\rangle(\langle k\rangle+1)。

Barabási《Network Science》第 8 章表 8.1 对十个参考网络比较了真实网络与随机化网络的 fcf_c：多数网络满足增强鲁棒性，例如蛋白相互作用网络随机失效 fc≈0.88f_c\approx0.88，对应随机化网络约 0.66，而按度攻击时只有约 0.06；度分布近似指数的电网（0.61 vs 0.63）则没有增强鲁棒性。

点失效与边失效

随机删边与随机删点的阈值相同（上一节已证明），但同样比例下删点造成的损伤更大：删去比例 ff 的节点平均相当于删去约 1−(1−f)21-(1-f)^2 比例的边（一条边只要任一端点被删就消失）。比较生物网络中的“蛋白缺失”（删点，如基因敲除）与“相互作用缺失”（删边，如破坏某个结合界面的点突变）时要注意这一差别。Zhong 等（2009，Molecular Systems Biology）分析约 5 万个已知的孟德尔病致病突变，把它们区分为“节点去除”与“边特异”（edgetic）扰动，并发现二者的功能后果不同。

“无标度网络 fc→1f_c\to1”是 N→∞N\to\infty 且无度相关的极限结论。生物网络节点数有限（数千到两万），度分布是否为幂律本身存疑（见小世界与无标度的统计判别），而且观测网络有大量缺失边。应当直接对观测网络做模拟，把“比随机化网络更鲁棒”作为可检验的命题，而不是从“无标度”推断“极鲁棒”。

继续阅读