Robustness of complex networks

Last updated April 07, 2024

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.^[1] For biologists, network robustness can help the study of diseases and mutations, and how to recover from some mutations.^[2] In economics, network robustness principles can help understanding of the stability and risks of banking systems.^[3] And in engineering, network robustness can help to evaluate the resilience of infrastructure networks such as the Internet or power grids.^[4]

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 $p_{c}$ .^[5] 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 $\langle s\rangle$ . This quantity represents the average size of all finite clusters and is given by the following equation.

${\begin{aligned}\langle s\rangle \sim \left|p-p_{c}\right|^{\gamma _{p}}\end{aligned}}$

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 $\gamma _{p}$ is universal for all lattices, while $p_{c}$ 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.

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.^[6]

${\begin{aligned}\kappa \equiv {\frac {\langle k^{2}\rangle }{\langle k\rangle }}>2\end{aligned}}$

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

${\begin{aligned}f_{c}=1-{\frac {1}{{\frac {\langle k^{2}\rangle }{\langle k\rangle }}-1}}\end{aligned}}$

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 $\langle k^{2}\rangle =\langle k\rangle (\langle k\rangle +1)$ for an Erdős–Rényi (ER) random graph, one can re-express the critical point for a random network.^[8]

${\begin{aligned}f_{c}^{ER}=1-{\frac {1}{\langle k\rangle }}\end{aligned}}$

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.^[8]

${\begin{aligned}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 >3\\A&=K_{max}^{3-\gamma }K_{min}^{\gamma -2},~3>\gamma >2\\A&=K_{max},~2>\gamma >1\\&where~K_{max}=K_{min}N^{\frac {1}{\gamma -1}}\end{aligned}}$

For $\gamma >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 <3$ , $\kappa$ 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.

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.^[9]

${\begin{aligned}f_{c}^{\frac {2-\gamma }{1-\gamma }}=2+{\frac {2-\gamma }{3-\gamma }}K_{min}(f_{c}^{\frac {3-\gamma }{1-\gamma }}-1)\end{aligned}}$

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.

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.^[10]^[11]^[12]^[13]^[14]^[15]^[16]^[17] 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.^[8]

For more detailed information on modeling cascading failures, see the global cascades model page.

Related Research Articles

<span class="mw-page-title-main">Negative binomial distribution</span> Probability distribution

In probability theory and statistics, the negative binomial distribution is a discrete probability distribution that models the number of failures in a sequence of independent and identically distributed Bernoulli trials before a specified (non-random) number of successes occurs. For example, we can define rolling a 6 on a dice as a success, and rolling any other number as a failure, and ask how many failure rolls will occur before we see the third success. In such a case, the probability distribution of the number of failures that appear will be a negative binomial distribution.

In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected clusters merge into significantly larger connected, so-called spanning clusters. The applications of percolation theory to materials science and in many other disciplines are discussed here and in the articles Network theory and Percolation.

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as

In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties; this likelihood tends to be greater than the average probability of a tie randomly established between two nodes.

Critical exponents describe the behavior of physical quantities near continuous phase transitions. It is believed, though not proven, that they are universal, i.e. they do not depend on the details of the physical system, but only on some of its general features. For instance, for ferromagnetic systems, the critical exponents depend only on:

In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.

In network theory, a giant component is a connected component of a given random graph that contains a significant fraction of the entire graph's vertices.

Fractal analysis is useful in the study of complex networks, present in both natural and artificial systems such as computer systems, brain and social networks, allowing further development of the field in network science.

A Boolean network consists of a discrete set of boolean variables each of which has a Boolean function assigned to it which takes inputs from a subset of those variables and output that determines the state of the variable it is assigned to. This set of functions in effect determines a topology (connectivity) on the set of variables, which then become nodes in a network. Usually, the dynamics of the system is taken as a discrete time series where the state of the entire network at time t+1 is determined by evaluating each variable's function on the state of the network at time t. This may be done synchronously or asynchronously.

In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who introduced one of the models in 1959. Edgar Gilbert introduced the other model contemporaneously with and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely. In the model introduced by Gilbert, also called the Erdős–Rényi–Gilbert model, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

The percolation threshold is a mathematical concept in percolation theory that describes the formation of long-range connectivity in random systems. Below the threshold a giant connected component does not exist; while above it, there exists a giant component of the order of system size. In engineering and coffee making, percolation represents the flow of fluids through porous media, but in the mathematics and physics worlds it generally refers to simplified lattice models of random systems or networks (graphs), and the nature of the connectivity in them. The percolation threshold is the critical value of the occupation probability p, or more generally a critical surface for a group of parameters p₁, p₂, ..., such that infinite connectivity (percolation) first occurs.

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

In the context of the physical and mathematical theory of percolation, a percolation transition is characterized by a set of universal critical exponents, which describe the fractal properties of the percolating medium at large scales and sufficiently close to the transition. The exponents are universal in the sense that they only depend on the type of percolation model and on the space dimension. They are expected to not depend on microscopic details such as the lattice structure, or whether site or bond percolation is considered. This article deals with the critical exponents of random percolation.

Hierarchical network models are iterative algorithms for creating networks which are able to reproduce the unique properties of the scale-free topology and the high clustering of the nodes at the same time. These characteristics are widely observed in nature, from biology to language to some social networks.

Global cascades models are a class of models aiming to model large and rare cascades that are triggered by exogenous perturbations which are relatively small compared with the size of the system. The phenomenon occurs ubiquitously in various systems, like information cascades in social systems, stock market crashes in economic systems, and cascading failure in physics infrastructure networks. The models capture some essential properties of such phenomenon.

The structural cut-off is a concept in network science which imposes a degree cut-off in the degree distribution of a finite size network due to structural limitations. Networks with vertices with degree higher than the structural cut-off will display structural disassortativity.

Quantum complex networks are complex networks whose nodes are quantum computing devices. Quantum mechanics has been used to create secure quantum communications channels that are protected from hacking. Quantum communications offer the potential for secure enterprise-scale solutions.

In network science, a critical point is a value of average degree, which separates random networks that have a giant component from those that do not. Considering a random network with an average degree $the critical point is$

Evolution of a random network is a dynamical process, usually leading to emergence of giant component accompanied with striking consequences on the network topology. To quantify this process, there is a need of inspection on how the size of the largest connected cluster within the network, $, varies with the average degree . Networks change their topology as they evolve, undergoing phase transitions. Phase transitions are generally known from physics, where it occurs as matter changes state according to its thermal energy level, or when ferromagnetic properties emerge in some materials as they are cooling down. Such phase transitions take place in matter because it is a network of particles, and as such, rules of network phase transition directly apply to it. Phase transitions in networks happen as links are added to a network, meaning that having N nodes, in each time increment, a link is placed between a randomly chosen pair of them. The transformation from a set of disconnected nodes to a fully connected network is called the evolution of a network.$

In network science, the configuration model is a method for generating random networks from a given degree sequence. It is widely used as a reference model for real-life social networks, because it allows the modeler to incorporate arbitrary degree distributions.

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. CiteSeerX 10.1.1.418.6489 . doi:10.1038/nature09659. PMID 21248842. S2CID 8264608.
↑ 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. S2CID 18811015.
↑ 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–4628. arXiv: cond-mat/0007048 . Bibcode:2000PhRvL..85.4626C. doi:10.1103/physrevlett.85.4626. PMID 11082612. S2CID 15372152.
1 2 3 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–3685. arXiv: cond-mat/0010251 . Bibcode:2001PhRvL..86.3682C. doi:10.1103/physrevlett.86.3682. PMID 11328053. S2CID 3852896.
↑ 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. S2CID 6042619.
↑ 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. S2CID 14550686.
↑ 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. S2CID 17189308.
↑ 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. S2CID 27573946.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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

[Motter2008-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. PMC 2267730 . PMID 18277384.

[Haldane2011-3] Haldane, A. G.; May, R. M. (2011). "Systemic risk in banking ecosystems". Nature. 469 (7330): 351–355. Bibcode:2011Natur.469..351H. CiteSeerX 10.1.1.418.6489 . doi:10.1038/nature09659. PMID 21248842. S2CID 8264608.

[Albert2004-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. S2CID 18811015.

[Stauffer1994-5] D. Stauffer and A. Aharony. Introduction to Percolation Theory. Tay-lor and Francis. London, 1994.

[Molloy1995-6] Molloy, M. and Reed, B. (1995) Random Structures and Algorithms 6, 161–180.

[Cohen2000-7] Cohen, R.; Erez, K.; Havlin, S. (2000). "Resilience of the Internet to random breakdowns". Phys. Rev. Lett. 85 (21): 4626–4628. arXiv: cond-mat/0007048 . Bibcode:2000PhRvL..85.4626C. doi:10.1103/physrevlett.85.4626. PMID 11082612. S2CID 15372152.

[NetworkBook-8] 1 2 3 ALBERT-LÁSZLÓ BARABÁSI. Network Science (2014).

[Cohen2001-9] Cohen, R.; Erez, K.; ben-Avraham, D.; Havlin, S. (2001). "Breakdown of the Internet under intentional attack". Phys. Rev. Lett. 86 (16): 3682–3685. arXiv: cond-mat/0010251 . Bibcode:2001PhRvL..86.3682C. doi:10.1103/physrevlett.86.3682. PMID 11328053. S2CID 3852896.

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

[Watts2002-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. S2CID 6042619.

[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. S2CID 14550686.

[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. S2CID 17189308.

[Kong2010-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. S2CID 27573946.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]