“鲁棒性”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第6行： 第6行：
  
  
−
复杂网络的鲁棒性研究对许多领域都非常重要。在生态学中，鲁棒性是生态系统的重要属性，可以使人们深入了解对诸如物种灭绝等干扰因素的反应<ref name="Sole2001">{{cite journal|author1=V. R. Sole |author2=M. M. Jose |title=Complexity and fragility in ecological net-works|journal=Proc. R. Soc. Lond. B|volume=268|issue=1480 |pages=2039–45|year=2001|pmid=11571051|doi=10.1098/rspb.2001.1767|pmc=1088846|arxiv=cond-mat/0011196}}</ref>。对于生物学家而言，网络鲁棒性可以帮助研究疾病和突变，以及如何从某些突变中恢复过来<ref name="Motter2008">{{cite journal|author1=A. Motter |author2=N. Gulbahce |author3=E. Almaas |author4=A.-L. Barabási |name-list-style=amp |title=Predicting synthetic rescues in metabolic networks|journal=Molecular Systems Biology|volume=4|pages=1–10|year=2008|doi=10.1038/msb.2008.1|pmid=18277384 |pmc=2267730|arxiv=0803.0962}}</ref> 。对于经济学，网络鲁棒性原则可以帮助理解银行系统的稳定性和风险<ref name="Haldane2011">{{cite journal |last1=Haldane |first1=A. G. |last2=May |first2=R. M. |year=2011 |title=Systemic risk in banking ecosystems |journal=Nature |volume=469 |issue=7330|pages=351–355 |doi=10.1038/nature09659|pmid=21248842 |bibcode=2011Natur.469..351H }}</ref>。同时在工程中，网络鲁棒性可以帮助评估基础建设网络（如互联网或电网）的恢复能力。<ref name="Albert2004">{{cite journal |last1=Albert |first1=R. |last2=Albert |first2=I. |last3=Nakarado |first3=G.L. |year=2004 |title=Structural Vulnerability of the North American Power Grid |journal=Phys. Rev. E |volume=69 |issue=2|page=025103 |doi=10.1103/physreve.69.025103|pmid=14995510 |arxiv=cond-mat/0401084 |bibcode=2004PhRvE..69b5103A }}</ref>
+
复杂网络的鲁棒性研究对许多领域都非常重要。在生态学中，鲁棒性是生态系统的重要属性，可以使人们深入了解对诸如物种灭绝等干扰因素的反应<ref name="Sole2001">{{cite journal|author1=V. R. Sole |author2=M. M. Jose |title=Complexity and fragility in ecological net-works|journal=Proc. R. Soc. Lond. B|volume=268|issue=1480 |pages=2039–45|year=2001|pmid=11571051|doi=10.1098/rspb.2001.1767|pmc=1088846|arxiv=cond-mat/0011196}}</ref>。对于生物学家而言，网络鲁棒性可以帮助研究疾病和突变，以及如何从某些突变中恢复过来<ref name="Motter2008">{{cite journal|author1=A. Motter |author2=N. Gulbahce |author3=E. Almaas |author4=A.-L. Barabási |name-list-style=amp |title=Predicting synthetic rescues in metabolic networks|journal=Molecular Systems Biology|volume=4|pages=1–10|year=2008|doi=10.1038/msb.2008.1|arxiv=0803.0962}}</ref> 。对于经济学，网络鲁棒性原则可以帮助理解银行系统的稳定性和风险<ref name="Haldane2011">{{cite journal |last1=Haldane |first1=A. G. |last2=May |first2=R. M. |year=2011 |title=Systemic risk in banking ecosystems |journal=Nature |volume=469 |issue=7330|pages=351–355 |doi=10.1038/nature09659|pmid=21248842 |bibcode=2011Natur.469..351H }}</ref>。同时在工程中，网络鲁棒性可以帮助评估基础建设网络（如互联网或电网）的恢复能力。<ref name="Albert2004">{{cite journal |last1=Albert |first1=R. |last2=Albert |first2=I. |last3=Nakarado |first3=G.L. |year=2004 |title=Structural Vulnerability of the North American Power Grid |journal=Phys. Rev. E |volume=69 |issue=2|page=025103 |doi=10.1103/physreve.69.025103|pmid=14995510 |arxiv=cond-mat/0401084 |bibcode=2004PhRvE..69b5103A }}</ref>
  
  

2021年2月4日 (四) 21:17的版本

此词条暂由Jie翻译


鲁棒性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]

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

References 参考文献

  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. doi:10.1038/msb.2008.1.
  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.
取自“https://wiki.swarma.org/index.php?title=鲁棒性&oldid=21581”