鲁棒性



鲁棒性Robustness(承受故障和干扰的能力)是许多复杂系统(包括复杂网络)的关键属性。


复杂网络的鲁棒性研究对许多领域都非常重要。在生态学中,鲁棒性是生态系统的重要属性,可以使人们深入了解对诸如物种灭绝等干扰因素的反应[1]。对于生物学家而言,网络鲁棒性可以帮助研究疾病和突变,以及如何从某些突变中恢复过来[2] 。对于经济学,网络鲁棒性原则可以帮助理解银行系统的稳定性和风险[3]。同时在工程中,网络鲁棒性可以帮助评估基础建设网络(如互联网或电网)的恢复能力。[4]


渗流理论

复杂网络的鲁棒性主要是关注移除节点或连接后的网络响应情况。可以将这个过程的数学模型视为逆渗透过程。渗流理论模拟了将小卵石以概率[math]\displaystyle{ p_c }[/math]随机放置在[math]\displaystyle{ n }[/math]维晶格上的过程,并以临界概率来预测突然形成单个簇群的过程[5] 。在渗流理论中,该簇群被称为渗流簇。这种现象可以通过许多参数来量化,例如平均簇大小[math]\displaystyle{ \langle s \rangle }[/math]。它表示所有有限簇的平均大小,并由以下方程式给出:


[math]\displaystyle{ \langle s \rangle \sim \left|p - p_c\right|^{\gamma_p} }[/math]


我们可以看到平均聚类大小的簇群突然在临界概率附近发散,表明形成了单个大簇群。需要注意的是指数 [math]\displaystyle{ \gamma_p }[/math] 对于所有晶格都是通用的,而 [math]\displaystyle{ p_c }[/math] 却不是的。这点非常重要,因为它表明在基于拓扑学观点上存在通用相变行为。可以将复杂网络中的鲁棒性问题视为渗透一个簇群开始,紧接着除去该簇群中卵石的关键部分最终以使该簇群瓦解。类似于渗流理论中渗流簇的形成,复杂网络的崩溃突然发生在相变过程中移除某些关键节点。


随机故障的临界阈值

关于复杂网络失去其庞大组成部分的阈值,其数学推导遵循 Molloy-Reed准则[6]:


[math]\displaystyle{ \kappa \equiv \frac{\langle k^2 \rangle}{\langle k \rangle} \gt 2 }[/math]



Molloy-Reed准则基于以下基本原理:为了形成一个巨大的组件,网络中的每个节点平均必须至少具有两个连接。这类似于每个人握住另外两个人的手以形成一条链。依据这一标准和相关的数学证明,对于复杂网络巨型组件的故障,可以得到一个需要移除的部分节点的临界阈值[7]


[math]\displaystyle{ f_c=1-\frac{1}{\frac{\langle k^2 \rangle}{\langle k \rangle}-1} }[/math]


该发现具有一个极其重要的性质,其临界阈值仅取决于度分布的一阶矩和二阶矩,并且对于任意分布均有效。


随机网络

使用 [math]\displaystyle{ \langle k^2 \rangle = \langle k \rangle(\langle k \rangle+1) }[/math] 表示 Erdős-Rényi(ER)随机图,可以重新表达随机网络的临界点[8]


[math]\displaystyle{ f_c^{ER}=1-\frac{1}{\langle k \rangle} }[/math]


随着随机网络变得越来越密集,临界阈值会增加,这意味着必须移除更高比例的节点才能断开巨型组件的连接。


无标度网络

通过将临界阈值重新表达为 无标度网络 Scale-free networkγ指数函数,我们可以得出有关无标度网络鲁棒性的两个重要结论[8]:


[math]\displaystyle{ \begin{align} f_c &=1-\frac{1}{\kappa-1}\\ \kappa &=\frac{\langle k^2\rangle}{\langle k \rangle}=\left|\frac{2-\gamma}{3-\gamma}\right|A \\ A &=K_{min},~\gamma \gt 3 \\ A &=K_{max}^{3-\gamma}K_{min}^{\gamma-2},~3 \gt \gamma \gt 2 \\ A &=K_{max},~2 \gt \gamma \gt 1 \\ &where~K_{max}=K_{min}N^{\frac{1}{\gamma - 1}} \end{align} }[/math]


对于大于3的[math]\displaystyle{ γ }[/math],临界阈值仅取决于[math]\displaystyle{ γ }[/math]和最小度。这种情况下,网络的部分节点被移除,之后该网络会像随机网络瓦解一般。对于小于3的[math]\displaystyle{ γ }[/math],随着[math]\displaystyle{ N }[/math]趋于无穷大,[math]\displaystyle{ \kappa }[/math]的极限会发散。在这种情况下,对于大型无标度网络,关键阈值接近1。从本质上讲,这意味着几乎要移除所有节点才能破坏巨型组件,该大型无标度网络在应对随机故障方面非常强大。通过考虑无标度网络尤其是枢纽的异构性,可以直观地理解这一点。由于相对较少的枢纽节点,因此不太可能通过随机故障将其移除,而较小的低度节点则更可能被移除。同时由于低度节点在连接巨型部件方面不重要,因此将其移除几乎没有多大影响。

无标度网络的针对性攻击

尽管无标度网络可以抵抗随机故障,但可以想象它对枢纽节点针对性的攻击其实非常脆弱。此时,我们就需要考虑无标度网络对目标攻击的鲁棒性,这需要在充分了解网络拓扑结构的前提下进行。通过研究删除枢纽节点时网络产生的变化,特别是最大程度与所连接节点的程度变化,我们就可以考虑到无标度网络上的针对性攻击,得出临界阈值的另一个公式[9]:


[math]\displaystyle{ \begin{align} f_c^{\frac{2-\gamma}{1-\gamma}}=2+\frac{2-\gamma}{3-\gamma}K_{min}(f_c^{\frac{3-\gamma}{1-\gamma}}-1) \end{align} }[/math]


该方程无法解析求解,但可以用数字表示。从中得出的结论是,当γ很大时,该网络可近似看作随机网络,其对抗攻击的鲁棒性变得类似于随机网络的随机故障鲁棒性。但是,当γ较小时,针对无标度网络攻击的临界阈值将变得相对较小,其抵抗定向攻击的脆弱性质逐渐显现出来。


有关复杂网络攻击耐受性的更多详细信息,请参阅攻击耐受性页面。

级联失效

许多网络中的故障的一个重要方面是,一个节点中的单个故障可能会导致相邻节点中的故障。当少量故障导致更多故障,导致相对于网络规模的大量故障时,就发生了级联故障。级联故障有很多模型[10][11][12][13][14][15][16][17] 。这些模型在许多细节上都不同,并且对从电源故障到Twitter上的信息流的不同物理传播现象进行建模,但是具有一些共享的原理。每个模型都专注于某种传播或级联,有一些阈值确定节点何时将发生故障或激活,并有助于传播,并且定义了某种机制,通过该机制,当节点发生故障或激活时将定向传播。所有这些模型都预测了某种临界状态,其中潜在级联的大小分布与幂律相匹配,并且指数由基础网络的度指数唯一确定。由于模型之间的差异以及结果的共识,我们认为潜在的现象是普遍的且与模型无关。[8]

有关建级联故障的更多详细信息,请参阅全局级联模型页面。

参考文献

  1. V. R. Sole; M. M. Jose (2001). "Complexity and fragility in ecological net-works". Proc. R. Soc. Lond. B. 268 (1480): 2039–45. arXiv:cond-mat/0011196. doi:10.1098/rspb.2001.1767. PMC 1088846. PMID 11571051.
  2. A. Motter; N. Gulbahce; E. Almaas; A.-L. Barabási (2008). "Predicting synthetic rescues in metabolic networks". Molecular Systems Biology. 4: 1–10. arXiv:0803.0962.
  3. Haldane, A. G.; May, R. M. (2011). "Systemic risk in banking ecosystems". Nature. 469 (7330): 351–355. Bibcode:2011Natur.469..351H. doi:10.1038/nature09659. PMID 21248842.
  4. Albert, R.; Albert, I.; Nakarado, G.L. (2004). "Structural Vulnerability of the North American Power Grid". Phys. Rev. E. 69 (2): 025103. arXiv:cond-mat/0401084. Bibcode:2004PhRvE..69b5103A. doi:10.1103/physreve.69.025103. PMID 14995510.
  5. D. Stauffer and A. Aharony. Introduction to Percolation Theory. Tay-lor and Francis. London, 1994.
  6. Molloy, M. and Reed, B. (1995) Random Structures and Algorithms 6, 161–180.
  7. Cohen, R.; Erez, K.; Havlin, S. (2000). "Resilience of the Internet to random breakdowns". Phys. Rev. Lett. 85 (21): 4626. arXiv:cond-mat/0007048. Bibcode:2000PhRvL..85.4626C. doi:10.1103/physrevlett.85.4626. PMID 11082612.
  8. 8.0 8.1 8.2 ALBERT-LÁSZLÓ BARABÁSI. Network Science (2014).
  9. Cohen, R.; Erez, K.; ben-Avraham, D.; Havlin, S. (2001). "Breakdown of the Internet under intentional attack". Phys. Rev. Lett. 86 (16): 3682. arXiv:cond-mat/0010251. Bibcode:2001PhRvL..86.3682C. doi:10.1103/physrevlett.86.3682. PMID 11328053.
  10. Dobson, I.; Carreras, B. A.; Lynch, V. E.; Newman, D. E. (2007). "Complex systems analysis of series of blackouts: Cascading failure, critical points, and self-organization". Chaos. 17 (2): 026103. Bibcode:2007Chaos..17b6103D. doi:10.1063/1.2737822. PMID 17614690.
  11. Dobson, I.; Carreras, A.; Newman, D.E. "A loading dependent model of probabilistic cascading failure. Probability in the". Engineering and Informational Sciences. 19 (15): 2005.
  12. Watts, D.J. (2002). "A simple model of global cascades on random networks". PNAS. 99 (9): 5766–5771. Bibcode:2002PNAS...99.5766W. doi:10.1073/pnas.082090499. PMC 122850. PMID 16578874.
  13. Goh, K.-I.; Lee, D.-S.; Kahng, B.; Kim, D. (2003). "Sandpile on scale-free net-works". Phys. Rev. Lett. 91 (14): 148701. arXiv:cond-mat/0305425. Bibcode:2003PhRvL..91n8701G. doi:10.1103/physrevlett.91.148701. PMID 14611564.
  14. Lee, D.-S.; Goh, K.-I.; Kahng, B.; Kim, D. (2004). "Sandpile avalanche dy-namics on scale-free networks". Physica A. 338 (1–2): 84. arXiv:cond-mat/0401531. Bibcode:2004PhyA..338...84L. doi:10.1016/j.physa.2004.02.028.
  15. Ding, M.; Yang, W. (1995). "Distribution of the first return time in frac-tional Brownian motion and its application to the study of onoff intermit-tency". Phys. Rev. E. 52 (1): 207–213. Bibcode:1995PhRvE..52..207D. doi:10.1103/physreve.52.207. PMID 9963421.
  16. Motter, Adilson E.; Lai, Ying-Cheng (20 December 2002). "Cascade-based attacks on complex networks". Physical Review E. 66 (6): 065102. arXiv:cond-mat/0301086. Bibcode:2002PhRvE..66f5102M. doi:10.1103/PhysRevE.66.065102. PMID 12513335.
  17. Kong, Z.; Yeh, E. M. (2010). "Resilience to Degree-Dependent and Cascad-ing Node Failures in Random Geometric Networks". IEEE Transactions on Information Theory. 56 (11): 5533. doi:10.1109/tit.2010.2068910.


编者推荐

课程推荐

陈关荣:网络中的鲁棒性

在该课程中,陈关荣老师主要讲解作为分析工具的渗流理论、无标度网络的鲁棒性、 网络对攻击的耐受性、网络受损后的级联故障原因及其建模、构筑具有坚强鲁棒性的网络的思路,以及讨论复杂网络鲁棒性与脆弱性的内在矛盾和本质原因。

生成缩略图出错:无法找到文件

巴拉巴西网络科学

本课程中,邀请了10位全国最顶尖的复杂科学专家为您全面系统讲解网络科学,帮助大家完成从散点思维到网络思维,直至网络科学思维的跃升。



本中文词条由Jie参与编译, Ruili 审校,思无涯咿呀咿呀编辑,欢迎在讨论页面留言。


本词条内容源自wikipedia及公开资料,遵守 CC3.0协议。