鲁棒性
此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。
Robustness, the ability to withstand failures and perturbations, is a critical attribute of many complex systems including complex networks.
Robustness, the ability to withstand failures and perturbations, is a critical attribute of many complex systems including complex networks.
鲁棒性（承受故障和干扰的能力）是许多复杂系统（包括复杂网络）的关键属性。
The study of robustness in complex networks is important for many fields. In ecology, robustness is an important attribute of ecosystems, and can give insight into the reaction to disturbances such as the extinction of species. For biologists, network robustness can help the study of diseases and mutations, and how to recover from some mutations. In economics, network robustness principles can help understanding of the stability and risks of banking systems. And in engineering, network robustness can help to evaluate the resilience of infrastructure networks such as the Internet or power grids.
The study of robustness in complex networks is important for many fields. In ecology, robustness is an important attribute of ecosystems, and can give insight into the reaction to disturbances such as the extinction of species. For biologists, network robustness can help the study of diseases and mutations, and how to recover from some mutations. In economics, network robustness principles can help understanding of the stability and risks of banking systems. And in engineering, network robustness can help to evaluate the resilience of infrastructure networks such as the Internet or power grids.
复杂网络的鲁棒性研究对许多领域都非常重要。在生态学中，鲁棒性是生态系统的重要属性，可以使人们深入了解诸如物种灭绝等干扰因素的反应。对于生物学家而言，网络鲁棒性可以帮助研究疾病和突变，以及如何从某些突变中恢复过来。对于经济学，网络鲁棒性原则可以帮助理解银行系统的稳定性和风险。同时在工程中，网络鲁棒性可以帮助评估基础建设网络（如互联网或电网）的恢复能力。
Percolation theory 渗流理论
The focus of robustness in complex networks is the response of the network to the removal of nodes or links. The mathematical model of such a process can be thought of as an inverse percolation process. Percolation theory models the process of randomly placing pebbles on an n-dimensional lattice with probability p, and predicts the sudden formation of a single large cluster at a critical probability [math]\displaystyle{ p_c }[/math]. In percolation theory this cluster is named the percolating cluster. This phenomenon is quantified in percolation theory by a number of quantities, for example the average cluster size [math]\displaystyle{ \langle s \rangle }[/math]. This quantity represents the average size of all finite clusters and is given by the following equation.
The focus of robustness in complex networks is the response of the network to the removal of nodes or links. The mathematical model of such a process can be thought of as an inverse percolation process. Percolation theory models the process of randomly placing pebbles on an n-dimensional lattice with probability p, and predicts the sudden formation of a single large cluster at a critical probability [math]\displaystyle{ p_c }[/math]. In percolation theory this cluster is named the percolating cluster. This phenomenon is quantified in percolation theory by a number of quantities, for example the average cluster size [math]\displaystyle{ \langle s \rangle }[/math]. This quantity represents the average size of all finite clusters and is given by the following equation.
复杂网络的鲁棒性主要是关注因删除节点或链接后的网络响应情况。可以将这个过程的数学模型视为逆渗透过程。渗流理论模拟了将小卵石以概率p随机放置在n维晶格上的过程，并以临界概率来预测突然形成单个簇群的过程。在渗流理论中，该簇群被称为渗流簇。这种现象可以通过许多参数来量化，例如平均聚类s。它表示所有有限簇的平均大小，并由以下方程式给出。
[math]\displaystyle{
\langle s \rangle \sim \left|p - p_c\right|^{\gamma_p}
}[/math]
We can see the average cluster size suddenly diverges around the critical probability, indicating the formation of a single large cluster. It is also important to note that the exponent [math]\displaystyle{ \gamma_p }[/math] is universal for all lattices, while [math]\displaystyle{ p_c }[/math] is not. This is important as it indicates a universal phase transition behavior, at a point dependent on the topology. The problem of robustness in complex networks can be seen as starting with the percolating cluster, and removing a critical fraction of the pebbles for the cluster to break down. Analogous to the formation of the percolation cluster in percolation theory, the breaking down of a complex network happens abruptly during a phase transition at some critical fraction of nodes removed.
We can see the average cluster size suddenly diverges around the critical probability, indicating the formation of a single large cluster. It is also important to note that the exponent [math]\displaystyle{ \gamma_p }[/math] is universal for all lattices, while [math]\displaystyle{ p_c }[/math] is not. This is important as it indicates a universal phase transition behavior, at a point dependent on the topology. The problem of robustness in complex networks can be seen as starting with the percolating cluster, and removing a critical fraction of the pebbles for the cluster to break down. Analogous to the formation of the percolation cluster in percolation theory, the breaking down of a complex network happens abruptly during a phase transition at some critical fraction of nodes removed.
我们可以看到平均团簇大小在临界概率附近突然分散，表明形成了一个单一的大团簇。同样需要注意的是，对于所有格来说，指数形式的 < math > gamma _ p </math > 是通用的，而 < math > p _ c </math > 则不是。这是重要的，因为它表明了一个普遍的相变行为，在一个点依赖于拓扑。复杂网络中的鲁棒性问题可以看作是从渗流集群开始，然后去掉集群中的一部分卵石以使其分解。类似于逾渗理论中逾渗团的形成，复杂网络在相变过程中突然发生破坏，这种破坏发生在节点的某个临界部分。
Critical threshold for random failures
The mathematical derivation for the threshold at which a complex network will lose its giant component is based on the Molloy–Reed criterion.[1]
The mathematical derivation for the threshold at which a complex network will lose its giant component is based on the Molloy–Reed criterion.
复杂网络失去巨分量阈值的数学推导是基于莫莱-里德准则。
[math]\displaystyle{ \lt math\gt 《数学》 \begin{align} \begin{align} 开始{ align } \kappa \equiv \frac{\langle k^2 \rangle}{\langle k \rangle} \gt 2 \kappa \equiv \frac{\langle k^2 \rangle}{\langle k \rangle} \gt 2 \kappa \equiv \frac{\langle k^2 \rangle}{\langle k \rangle} \gt 2 \end{align} \end{align} 结束{ align } }[/math]
</math>
数学
The Molloy–Reed criterion is derived from the basic principle that in order for a giant component to exist, on average each node in the network must have at least two links. This is analogous to each person holding two others' hands in order to form a chain. Using this criterion and an involved mathematical proof, one can derive a critical threshold for the fraction of nodes needed to be removed for the breakdown of the giant component of a complex network.[2]
The Molloy–Reed criterion is derived from the basic principle that in order for a giant component to exist, on average each node in the network must have at least two links. This is analogous to each person holding two others' hands in order to form a chain. Using this criterion and an involved mathematical proof, one can derive a critical threshold for the fraction of nodes needed to be removed for the breakdown of the giant component of a complex network.
莫洛伊-里德准则的基本原理是，为了使一个巨型部件存在，网络中的每个节点平均必须至少有两个链路。这类似于每个人牵着另外两个人的手形成一个链条。使用这个标准和一个复杂的数学证明，我们可以推导出一个临界阈值的节点的部分需要删除的分解复杂网络的巨大组成部分。
[math]\displaystyle{ \lt math\gt 《数学》 \begin{align} \begin{align} 开始{ align } f_c=1-\frac{1}{\frac{\langle k^2 \rangle}{\langle k \rangle}-1} f_c=1-\frac{1}{\frac{\langle k^2 \rangle}{\langle k \rangle}-1} 1-frac { frac { langle k ^ 2 rangle }{ langle k rangle }-1} \end{align} \end{align} 结束{ align } }[/math]
</math>
数学
An important property of this finding is that the critical threshold is only dependent on the first and second moment of the degree distribution and is valid for an arbitrary degree distribution.
An important property of this finding is that the critical threshold is only dependent on the first and second moment of the degree distribution and is valid for an arbitrary degree distribution.
这个结果的一个重要性质是临界阈值仅依赖于度分布的第一和第二阶矩，并且对于任意的度分布是有效的。
Random network
Using [math]\displaystyle{ \langle k^2 \rangle = \langle k \rangle(\langle k \rangle+1) }[/math] for an Erdős–Rényi (ER) random graph, one can re-express the critical point for a random network.[3]
Using [math]\displaystyle{ \langle k^2 \rangle = \langle k \rangle(\langle k \rangle+1) }[/math] for an Erdős–Rényi (ER) random graph, one can re-express the critical point for a random network.
利用随机图的 < math > > langle k ^ 2 rangle = langle k rangle (langle k rangle + 1) </math > ，可以重新表示随机网络的临界点。
[math]\displaystyle{ \lt math\gt 《数学》 \begin{align} \begin{align} 开始{ align } f_c^{ER}=1-\frac{1}{\langle k \rangle} f_c^{ER}=1-\frac{1}{\langle k \rangle} 1-frac {1}{ langle k rangle } \end{align} \end{align} 结束{ align } }[/math]
</math>
数学
As a random network gets denser, the critical threshold increases, meaning a higher fraction of the nodes must be removed to disconnect the giant component.
As a random network gets denser, the critical threshold increases, meaning a higher fraction of the nodes must be removed to disconnect the giant component.
随着随机网络的密度增加，临界阈值增加，这意味着必须删除更高的节点分数以断开巨型组件的连接。
Scale-free network
By re-expressing the critical threshold as a function of the gamma exponent for a scale-free network, we can draw a couple of important conclusions regarding scale-free network robustness.[3]
By re-expressing the critical threshold as a function of the gamma exponent for a scale-free network, we can draw a couple of important conclusions regarding scale-free network robustness.
通过将临界阈值重新表示为无尺度网络指数的函数，我们可以得出关于无尺度网络稳健性的两个重要结论。
[math]\displaystyle{ \lt math\gt 《数学》 \begin{align} \begin{align} 开始{ align } f_c &=1-\frac{1}{\kappa-1}\\ f_c &=1-\frac{1}{\kappa-1}\\ 1-frac {1}{ kappa-1} \kappa &=\frac{\langle k^2\rangle}{\langle k \rangle}=\left|\frac{2-\gamma}{3-\gamma}\right|A \\ \kappa &=\frac{\langle k^2\rangle}{\langle k \rangle}=\left|\frac{2-\gamma}{3-\gamma}\right|A \\ 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_{min},~\gamma \gt 3 \\ A & = k { min } ，~ gamma \gt 3 A &=K_{max}^{3-\gamma}K_{min}^{\gamma-2},~3 \gt \gamma \gt 2 \\ A &=K_{max}^{3-\gamma}K_{min}^{\gamma-2},~3 \gt \gamma \gt 2 \\ A & = k _ { max } ^ {3-gamma } k _ { min } ^ { gamma-2} ，~ 3 \gt gamma \gt 2 A &=K_{max},~2 \gt \gamma \gt 1 \\ A &=K_{max},~2 \gt \gamma \gt 1 \\ A & = k { max } ，~ 2 \gt γ \gt 1 &where~K_{max}=K_{min}N^{\frac{1}{\gamma - 1}} &where~K_{max}=K_{min}N^{\frac{1}{\gamma - 1}} 其中 ~ k { max } = k { min } n ^ { frac {1}{ gamma-1} \end{align} \end{align} 结束{ align } }[/math]
</math>
数学
For gamma greater than 3, the critical threshold only depends on gamma and the minimum degree, and in this regime the network acts like a random network breaking when a finite fraction of its nodes are removed. For gamma less than 3, [math]\displaystyle{ \kappa }[/math] diverges in the limit as N trends toward infinity. In this case, for large scale-free networks, the critical threshold approaches 1. This essentially means almost all nodes must be removed in order to destroy the giant component, and large scale-free networks are very robust with regard to random failures. One can make intuitive sense of this conclusion by thinking about the heterogeneity of scale-free networks and of the hubs in particular. Because there are relatively few hubs, they are less likely to be removed through random failures while small low-degree nodes are more likely to be removed. Because the low-degree nodes are of little importance in connecting the giant component, their removal has little impact.
For gamma greater than 3, the critical threshold only depends on gamma and the minimum degree, and in this regime the network acts like a random network breaking when a finite fraction of its nodes are removed. For gamma less than 3, [math]\displaystyle{ \kappa }[/math] diverges in the limit as N trends toward infinity. In this case, for large scale-free networks, the critical threshold approaches 1. This essentially means almost all nodes must be removed in order to destroy the giant component, and large scale-free networks are very robust with regard to random failures. One can make intuitive sense of this conclusion by thinking about the heterogeneity of scale-free networks and of the hubs in particular. Because there are relatively few hubs, they are less likely to be removed through random failures while small low-degree nodes are more likely to be removed. Because the low-degree nodes are of little importance in connecting the giant component, their removal has little impact.
对于 γ 大于3的情况，临界阈值只取决于 γ 和最小度，在这种情况下，当有限部分的节点被移除时，网络就像一个随机的网络断裂。对于小于3的 γ，k 在极限处发散，n 趋向于无穷大。在这种情况下，对于大规模无标度网络，临界阈值接近1。这基本上意味着几乎所有的节点必须被删除，以摧毁巨大的组成部分，大规模无尺度网络是非常健壮的随机故障。通过考虑无标度网络的异质性，特别是枢纽的异质性，人们可以对这一结论有直观的理解。由于集线器相对较少，它们不太可能通过随机故障被移除，而小的低度节点更有可能被移除。由于低度节点对于连接巨型构件的重要性不大，因此去除这些节点的影响不大。
Targeted attacks on scale-free networks
Although scale-free networks are resilient to random failures, we might imagine them being quite vulnerable to targeted hub removal. In this case we consider the robustness of scale free networks in response to targeted attacks, performed with thorough prior knowledge of the network topology. By considering the changes induced by the removal of a hub, specifically the change in the maximum degree and the degrees of the connected nodes, we can derive another formula for the critical threshold considering targeted attacks on a scale free network.[4]
Although scale-free networks are resilient to random failures, we might imagine them being quite vulnerable to targeted hub removal. In this case we consider the robustness of scale free networks in response to targeted attacks, performed with thorough prior knowledge of the network topology. By considering the changes induced by the removal of a hub, specifically the change in the maximum degree and the degrees of the connected nodes, we can derive another formula for the critical threshold considering targeted attacks on a scale free network.
尽管无标度网络对于随机故障具有弹性，但我们可以想象它们对于有针对性的中心移除是非常脆弱的。在这种情况下，我们考虑了无标度网络对于目标攻击的鲁棒性，这些攻击是在完全了解网络拓扑的情况下进行的。通过考虑移除枢纽引起的变化，特别是连通节点的最大度和度的变化，我们可以推导出无标度网络上考虑目标攻击的临界阈值公式。
[math]\displaystyle{ \lt math\gt 《数学》 \begin{align} \begin{align} 开始{ align } f_c^{\frac{2-\gamma}{1-\gamma}}=2+\frac{2-\gamma}{3-\gamma}K_{min}(f_c^{\frac{3-\gamma}{1-\gamma}}-1) f_c^{\frac{2-\gamma}{1-\gamma}}=2+\frac{2-\gamma}{3-\gamma}K_{min}(f_c^{\frac{3-\gamma}{1-\gamma}}-1) 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} \end{align} 结束{ align } }[/math]
</math>
数学
This equation cannot be solved analytically, but can be graphed numerically. To summarize the important points, when gamma is large, the network acts as a random network, and attack robustness become similar to random failure robustness of a random network. However, when gamma is smaller, the critical threshold for attacks on scale-free networks becomes relatively small, indicating a weakness to targeted attacks.
This equation cannot be solved analytically, but can be graphed numerically. To summarize the important points, when gamma is large, the network acts as a random network, and attack robustness become similar to random failure robustness of a random network. However, when gamma is smaller, the critical threshold for attacks on scale-free networks becomes relatively small, indicating a weakness to targeted attacks.
这个方程不能用解析方法求解，而可用数值方法进行表示。综上所述，当伽马值较大时，网络表现为一个随机网络，攻击鲁棒性与随机网络的随机故障鲁棒性相似。然而，当伽马值较小时，无标度网络的攻击临界阈值变得相对较小，表明无标度网络的攻击弱于目标攻击。
For more detailed information on the attack tolerance of complex networks please see the attack tolerance page.
For more detailed information on the attack tolerance of complex networks please see the attack tolerance page.
有关复杂网络的攻击容忍度的更多详细信息，请参阅攻击容忍页面。
Cascading failures
An important aspect of failures in many networks is that a single failure in one node might induce failures in neighboring nodes. When a small number of failures induces more failures, resulting in a large number of failures relative to the network size, a cascading failure has occurred. There are many models for cascading failures.[5][6][7][8][9][10][11][12] These models differ in many details, and model different physical propagation phenomenon from power failures to information flow over Twitter, but have some shared principals. Each model focuses on some sort of propagation or cascade, there is some threshold determining when a node will fail or activate and contribute towards propagation, and there is some mechanism defined by which propagation will be directed when nodes fail or activate. All of these models predict some critical state, in which the distribution of the size of potential cascades matches a power law, and the exponent is uniquely determined by the degree exponent of the underlying network. Because of the differences in the models and the consensus of this result, we模板:Who are led to believe the underlying phenomenon is universal and model-independent.[3]
An important aspect of failures in many networks is that a single failure in one node might induce failures in neighboring nodes. When a small number of failures induces more failures, resulting in a large number of failures relative to the network size, a cascading failure has occurred. There are many models for cascading failures. These models differ in many details, and model different physical propagation phenomenon from power failures to information flow over Twitter, but have some shared principals. Each model focuses on some sort of propagation or cascade, there is some threshold determining when a node will fail or activate and contribute towards propagation, and there is some mechanism defined by which propagation will be directed when nodes fail or activate. All of these models predict some critical state, in which the distribution of the size of potential cascades matches a power law, and the exponent is uniquely determined by the degree exponent of the underlying network. Because of the differences in the models and the consensus of this result, we are led to believe the underlying phenomenon is universal and model-independent.
在许多网络中，失败的一个重要方面是一个节点的单一失败可能会导致相邻节点的失败。当少量的故障导致更多的故障，导致相对于网络大小的大量故障时，就会发生级联故障。对于连锁故障有许多模型。这些模型在许多细节上有所不同，并且模拟了从电源故障到 Twitter 上的信息流等不同的物理传播现象，但是有一些共享的原则。每个模型都关注于某种传播或级联，有一些阈值来决定一个节点何时会失败或激活并促进传播，还有一些机制定义了当节点失败或激活时，传播将被定向。所有这些模型都预测了一些临界状态，在这些临界状态中，势级联的大小分布符合幂律，指数由底层网络的度指数唯一决定。由于模型之间的差异和对这一结果的共识，我们相信潜在的现象是普遍的和模型独立的。
For more detailed information on modeling cascading failures, see the global cascades model page.
For more detailed information on modeling cascading failures, see the global cascades model page.
有关对级联故障建模的详细信息，请参阅全局级联模型页面。
References
- ↑ 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.
- ↑ 3.0 3.1 3.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.
Category:Network theory
范畴: 网络理论
Category:Reliability analysis
类别: 可靠性分析
This page was moved from wikipedia:en:Robustness of complex networks. Its edit history can be viewed at 鲁棒性/edithistory