2,443
个编辑
更改
无编辑摘要
复杂网络的鲁棒性研究对许多领域都非常重要。在生态学中，鲁棒性是生态系统的重要属性，可以使人们深入了解对诸如物种灭绝等干扰因素的反应<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>
== 渗流理论 ==
== 渗流理论 ==
复杂网络的鲁棒性主要是关注移除节点或链接后的网络响应情况。可以将这个过程的数学模型视为逆渗透过程。渗流理论模拟了将小卵石以概率<math>p_c</math>随机放置在<math>n</math>维晶格上的过程，并以临界概率来预测突然形成单个簇群的过程。在渗流理论中，该簇群被称为渗流簇。这种现象可以通过许多参数来量化，例如平均簇大小<math>\langle s \rangle</math>。它表示所有有限簇的平均大小，并由以下方程式给出:
复杂网络的鲁棒性主要是关注移除节点或链接后的网络响应情况。可以将这个过程的数学模型视为逆渗透过程。渗流理论模拟了将小卵石以概率<math>p_c</math>随机放置在<math>n</math>维晶格上的过程，并以临界概率来预测突然形成单个簇群的过程<ref name="Stauffer1994">D. Stauffer and A. Aharony. Introduction to Percolation Theory. Tay-lor and Francis. London, 1994.</ref> 。在渗流理论中，该簇群被称为渗流簇。这种现象可以通过许多参数来量化，例如平均簇大小<math>\langle s \rangle</math>。它表示所有有限簇的平均大小，并由以下方程式给出:
关于复杂网络失去其庞大组成部分的阈值，其数学推导遵循'''<font color="#ff8000"> Molloy-Reed准则</font>''':
关于复杂网络失去其庞大组成部分的阈值，其数学推导遵循'''<font color="#ff8000"> Molloy-Reed准则</font>'''<ref name="Molloy1995">Molloy, M. and Reed, B. (1995) ''Random Structures and Algorithms 6'', 161–180.</ref>:
'''<font color="#ff8000"> Molloy-Reed准则</font>'''基于以下基本原理：为了形成一个巨大的组件，网络中的每个节点平均必须至少具有两个链接。这类似于每个人握住另外两个人的手以形成一条链。依据这一标准和相关的数学证明，对于复杂网络巨型组件的故障，可以得到一个需要移除的部分节点的临界阈值。
'''<font color="#ff8000"> Molloy-Reed准则</font>'''基于以下基本原理：为了形成一个巨大的组件，网络中的每个节点平均必须至少具有两个链接。这类似于每个人握住另外两个人的手以形成一条链。依据这一标准和相关的数学证明，对于复杂网络巨型组件的故障，可以得到一个需要移除的部分节点的临界阈值<ref name="Cohen2000">{{cite journal |last1=Cohen |first1=R. |last2=Erez |first2=K. |last3=Havlin |first3=S. |title=Resilience of the Internet to random breakdowns |journal=Phys. Rev. Lett. |volume=85 |issue=21 |page=4626|year=2000 |doi=10.1103/physrevlett.85.4626 |bibcode=2000PhRvL..85.4626C|arxiv=cond-mat/0007048 |pmid=11082612}}</ref>
。
使用 <math>\langle k^2 \rangle = \langle k \rangle(\langle k \rangle+1)</math> 表示'''<font color="#ff8000"> Erdős-Rényi（ER）随机图</font>'''，可以重新表达随机网络的临界点。
使用 <math>\langle k^2 \rangle = \langle k \rangle(\langle k \rangle+1)</math> 表示'''<font color="#ff8000"> Erdős-Rényi（ER）随机图</font>'''，可以重新表达随机网络的[[临界点]]。<ref name="NetworkBook">ALBERT-LÁSZLÓ BARABÁSI. Network Science (2014).</ref>
通过将临界阈值重新表达为'''<font color="#ff8000"> [[无标度网络]] Scale-free network</font>'''的''γ''指数函数，我们可以得出有关无标度网络鲁棒性的两个重要结论:
通过将临界阈值重新表达为'''<font color="#ff8000"> [[无标度网络]] Scale-free network</font>'''的''γ''指数函数，我们可以得出有关无标度网络鲁棒性的两个重要结论<ref name="NetworkBook"/>:
尽管无标度网络可以抵抗随机故障，但可以想象它对枢纽节点针对性的攻击其实非常脆弱。此时，我们就需要考虑无标度网络对目标攻击的鲁棒性，这需要在充分了解网络拓扑结构的前提下进行。通过研究删除枢纽节点时网络产生的变化，特别是最大程度与所连接节点的程度变化，我们就可以考虑到无标度网络上的针对性攻击，得出临界阈值的另一个公式:
尽管无标度网络可以抵抗随机故障，但可以想象它对枢纽节点针对性的攻击其实非常脆弱。此时，我们就需要考虑无标度网络对目标攻击的鲁棒性，这需要在充分了解网络拓扑结构的前提下进行。通过研究删除枢纽节点时网络产生的变化，特别是最大程度与所连接节点的程度变化，我们就可以考虑到无标度网络上的针对性攻击，得出临界阈值的另一个公式<ref name="Cohen2001">{{cite journal |last1=Cohen |first1=R. |last2=Erez |first2=K. |last3=ben-Avraham |first3=D. |last4=Havlin |first4=S. |title=Breakdown of the Internet under intentional attack |journal=Phys. Rev. Lett. |volume=86 |issue=16 |page=3682|year=2001 |doi=10.1103/physrevlett.86.3682 |bibcode=2001PhRvL..86.3682C|arxiv=cond-mat/0010251 |pmid=11328053}}</ref>:
许多网络中的故障的一个重要方面是，一个节点中的单个故障可能会导致相邻节点中的故障。当少量故障导致更多故障，导致相对于网络规模的大量故障时，就发生了级联故障。级联故障有很多模型<ref>{{cite journal |last1=Dobson |first1=I. |last2=Carreras |first2=B. A. |last3=Lynch |first3=V. E. |last4=Newman |first4=D. E. |year=2007 |title=Complex systems analysis of series of blackouts: Cascading failure, critical points, and self-organization |journal=Chaos |volume=17 |issue=2|page=026103 |doi=10.1063/1.2737822|pmid=17614690 |bibcode=2007Chaos..17b6103D }}</ref><ref>{{cite journal |last1=Dobson |first1=I. |last2=Carreras |first2=A. |last3=Newman |first3=D.E. |title=A loading dependent model of probabilistic cascading failure. Probability in the |journal=Engineering and Informational Sciences |volume=19 |issue=15|page=2005 }}</ref><ref name="Watts2002">{{cite journal |last1=Watts |first1=D.J. |title=A simple model of global cascades on random networks |doi=10.1073/pnas.082090499 |pmid=16578874 |journal=PNAS |volume=99 |issue=9 |pages=5766–5771 |year=2002 |pmc=122850 |bibcode=2002PNAS...99.5766W }}</ref><ref>{{cite journal |last1=Goh |first1=K.-I. |last2=Lee |first2=D.-S. |last3=Kahng |first3=B. |last4=Kim |first4=D. |year=2003 |title=Sandpile on scale-free net-works |journal=Phys. Rev. Lett. |volume=91 |issue=14|page=148701 |doi=10.1103/physrevlett.91.148701 |pmid=14611564 |bibcode=2003PhRvL..91n8701G|arxiv=cond-mat/0305425 }}</ref><ref>{{cite journal |last1=Lee |first1=D.-S. |last2=Goh |first2=K.-I. |last3=Kahng |first3=B. |last4=Kim |first4=D. |title=Sandpile avalanche dy-namics on scale-free networks |journal=Physica A |volume=338 |issue=1–2 |page=84|year=2004 |doi=10.1016/j.physa.2004.02.028 |arxiv=cond-mat/0401531 |bibcode=2004PhyA..338...84L }}</ref><ref>{{cite journal |last1=Ding |first1=M. |last2=Yang |first2=W. |year=1995 |title=Distribution of the first return time in frac-tional Brownian motion and its application to the study of onoff intermit-tency |journal=Phys. Rev. E |volume=52 |issue=1|pages=207–213 |doi=10.1103/physreve.52.207|pmid=9963421 |bibcode=1995PhRvE..52..207D }}</ref><ref>{{cite journal |last1=Motter |first1=Adilson E. |last2=Lai |first2=Ying-Cheng |title=Cascade-based attacks on complex networks |journal=Physical Review E |date=20 December 2002 |volume=66 |issue=6 |pages=065102 |doi=10.1103/PhysRevE.66.065102 |pmid=12513335 |arxiv=cond-mat/0301086|bibcode=2002PhRvE..66f5102M }}</ref><ref name="Kong2010">{{cite journal |last1=Kong |first1=Z. |last2=Yeh |first2=E. M. |title=Resilience to Degree-Dependent and Cascad-ing Node Failures in Random Geometric Networks |journal=IEEE Transactions on Information Theory |volume=56 |issue=11 |page=5533|year=2010 |doi=10.1109/tit.2010.2068910}}</ref> 。这些模型在许多细节上都不同，并且对从电源故障到Twitter上的信息流的不同物理传播现象进行建模，但是具有一些共享的原理。每个模型都专注于某种传播或级联，有一些阈值确定节点何时将发生故障或激活，并有助于传播，并且定义了某种机制，通过该机制，当节点发生故障或激活时将定向传播。所有这些模型都预测了某种临界状态，其中潜在级联的大小分布与[[幂律]]相匹配，并且指数由基础网络的度指数唯一确定。由于模型之间的差异以及结果的共识，我们认为潜在的现象是普遍的且与模型无关。<ref name="NetworkBook"/>
有关建级联故障的更多详细信息，请参阅[https://en.wikipedia.org/wiki/Global_cascades_model 全局级联模型]页面。
有关建级联故障的更多详细信息，请参阅[https://en.wikipedia.org/wiki/Global_cascades_model 全局级联模型]页面。