鲁棒性

此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。

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.

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

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]\displaystyle{ \gamma_p }[/math] 对于所有晶格都是通用的，而 [math]\displaystyle{ 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.

The mathematical derivation for the threshold at which a complex network will lose its giant component is based on the Molloy–Reed criterion.

关于复杂网络失去其庞大组成部分的触发阈值，其数学推导遵循 Molloy-Reed准则。

[math]\displaystyle{ \kappa \equiv \frac{\langle k^2 \rangle}{\langle k \rangle} \gt 2 }[/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.

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.

Molloy-Reed准则基于以下基本原理：为了形成一个巨大的组件，网络中的每个节点平均必须至少具有两个链接。这类似于每个人握住两只手以形成一条链。依据这一标准和相关的数学证明，对于复杂网络巨型组件的故障，可以通过删除其中部分节点来得出一个临界阈值。该发现具有一个极其重要的性质，其临界阈值仅取决于度分布的第一和第二矩，并且对于任意度分布均有效。

[math]\displaystyle{ f_c=1-\frac{1}{\frac{\langle k^2 \rangle}{\langle k \rangle}-1} }[/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.

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]\displaystyle{ \langle k^2 \rangle = \langle k \rangle(\langle k \rangle+1) }[/math] 表示 Erdős-Rényi（ER）随机图，可以重新表达随机网络的临界点。

[math]\displaystyle{ f_c^{ER}=1-\frac{1}{\langle k \rangle} }[/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.

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.

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

[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]

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的伽玛γ，随着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.

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{ \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]

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. 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.

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

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