“鲁棒性”的版本间的差异
（→无标度网络） |
|||
| 第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> | |
| 第12行： | 第12行： | ||
== 渗流理论 == | == 渗流理论 == | ||
| − | 复杂网络的鲁棒性主要是关注移除节点或链接后的网络响应情况。可以将这个过程的数学模型视为逆渗透过程。渗流理论模拟了将小卵石以概率<math>p_c</math>随机放置在<math>n</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>。它表示所有有限簇的平均大小，并由以下方程式给出: |
| 第29行： | 第29行： | ||
| − | 关于复杂网络失去其庞大组成部分的阈值，其数学推导遵循'''<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>: |
| 第41行： | 第41行： | ||
| − | '''<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> |
| + | 。 | ||
| 第59行： | 第60行： | ||
| − | 使用 <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> |
| + | |||
| 第77行： | 第79行： | ||
| − | 通过将临界阈值重新表达为'''<font color="#ff8000"> [[无标度网络]] Scale-free network</font>'''的''γ''指数函数，我们可以得出有关无标度网络鲁棒性的两个重要结论: | + | 通过将临界阈值重新表达为'''<font color="#ff8000"> [[无标度网络]] Scale-free network</font>'''的''γ''指数函数，我们可以得出有关无标度网络鲁棒性的两个重要结论<ref name="NetworkBook"/>: |
| 第109行： | 第111行： | ||
| − | 尽管无标度网络可以抵抗随机故障，但可以想象它对枢纽节点针对性的攻击其实非常脆弱。此时，我们就需要考虑无标度网络对目标攻击的鲁棒性，这需要在充分了解网络拓扑结构的前提下进行。通过研究删除枢纽节点时网络产生的变化，特别是最大程度与所连接节点的程度变化，我们就可以考虑到无标度网络上的针对性攻击，得出临界阈值的另一个公式: | + | 尽管无标度网络可以抵抗随机故障，但可以想象它对枢纽节点针对性的攻击其实非常脆弱。此时，我们就需要考虑无标度网络对目标攻击的鲁棒性，这需要在充分了解网络拓扑结构的前提下进行。通过研究删除枢纽节点时网络产生的变化，特别是最大程度与所连接节点的程度变化，我们就可以考虑到无标度网络上的针对性攻击，得出临界阈值的另一个公式<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>: |
| 第132行： | 第134行： | ||
| − | + | 许多网络中的故障的一个重要方面是，一个节点中的单个故障可能会导致相邻节点中的故障。当少量故障导致更多故障，导致相对于网络规模的大量故障时，就发生了级联故障。级联故障有很多模型<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 全局级联模型]页面。 | ||
2021年2月4日 (四) 21:16的版本
此词条暂由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 参考文献
- ↑ 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.
- ↑ 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. PMC 2267730. PMID 18277384.
- ↑ 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.
- ↑ 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.
- ↑ D. Stauffer and A. Aharony. Introduction to Percolation Theory. Tay-lor and Francis. London, 1994.
- ↑ Molloy, M. and Reed, B. (1995) Random Structures and Algorithms 6, 161–180.
- ↑ 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.0 8.1 8.2 ALBERT-LÁSZLÓ BARABÁSI. Network Science (2014).
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.