# Universal behavior of cascading failures in interdependent networks

^{a}School of Mechanical Engineering, Northwestern Polytechnical University, Xi’an 710072, China;^{b}School of Information and Control Engineering, Xi’an University of Architecture and Technology, Xi’an 710311, China;^{c}Center for OPTical IMagery Analysis and Learning, Northwestern Polytechnical University, Xi’an 710072, China;^{d}School of Reliability and Systems Engineering, Beihang University, Beijing 100191, China;^{e}Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 12180;^{f}Network Science and Technology Center, Rensselaer Polytechnic Institute, Troy, NY 12180;^{g}Department of Physics, Bar-Ilan University, Ramat-Gan 52900, Israel;^{h}Center for Polymer Studies, Department of Physics, Boston University, Boston, MA 02215;^{i}Institute of Complex Systems, Consiglio Nazionale delle Ricerche, Florence 50019, Italy;^{j}Unmanned Systems Research Institute, Northwestern Polytechnical University, Xi’an 710072, China

See allHide authors and affiliations

Contributed by H. Eugene Stanley, August 11, 2019 (sent for review March 14, 2019; reviewed by Santo Fortunato and Vito Latora)

## Significance

Catastrophic events affecting technological or critical infrastructures are often originated by a cascading failure triggered by marginal perturbations, which are on their turn localized in one of the many interdependent graphs describing the systems. Understanding the robustness of these graphs is therefore of utmost importance for preventing crashes and/or for engineering more efficient and stalwart networked systems. Here we give a fresh framework by means of which cascading failures can be described in a very rich variety of dynamical models and/or topological network structures and which provides a series of quantitative answers able to predict the extent of the system’s failure.

## Abstract

Catastrophic and major disasters in real-world systems, such as blackouts in power grids or global failures in critical infrastructures, are often triggered by minor events which originate a cascading failure in interdependent graphs. We present here a self-consistent theory enabling the systematic analysis of cascading failures in such networks and encompassing a broad range of dynamical systems, from epidemic spreading, to birth–death processes, to biochemical and regulatory dynamics. We offer testable predictions on breakdown scenarios, and, in particular, we unveil the conditions under which the percolation transition is of the first-order or the second-order type, as well as prove that accounting for dynamics in the nodes always accelerates the cascading process. Besides applying directly to relevant real-world situations, our results give practical hints on how to engineer more robust networked systems.

In recent years, lots of studies concentrated on catastrophic events affecting the Internet, power grids, or other critical infrastructures (1⇓⇓⇓⇓–6). Most such major disasters are in fact triggered by minor events, which may originate a cascading failure in interdependent graphs (7⇓⇓⇓⇓–12). Understanding the robustness of these networks with respect to minor perturbations is of utmost importance for preventing system crashes (13, 14). An example is power and communication networks: Power stations administer energy to communication nodes and depend on them at the same time for control, so that malfunctions may spread from one network to the other (15). Cascading failures have been studied intensively in statistical physics on single graphs or on networks that interact with (and/or depend on) each other (16, 17).

To capture the spreading mechanisms in such graphs, one needs a mathematical scaffold able to seize 2 basic aspects: the structural and functional interdependence between the networks, and the spreading of failures within each single graph. So far, the first issue was dealt with by examining changes in the structure connectivity caused by node dependence between networks (12, 15, 18), and the critical properties of the failure process were unveiled with the help of percolation theory (19⇓⇓⇓–23). Interdependency between network constituents fundamentally alter the percolation properties (8, 24⇓⇓⇓⇓⇓–30). In particular, Parshani et al. (22) found that, when a critical fraction of nodes in one network fails at a weak (strong) interdependence level between the networks, the system undergoes a second-order (first-order) phase transition due to recursive processes of cascading failures. As for the second issue, studies concentrated on the conditions and outcome for cascading failures (31⇓⇓–34). Different from structural failures caused by removed nodes, overload failures usually propagate in the system through invisible paths (35⇓⇓⇓⇓–40). In particular, Barzel and Barabási (39) developed a self-consistent theory able to analyze the case of a perturbation localized in one node which spreads within the structure of the graph.

In this paper, we contribute a fresh mathematical framework for cascading failures, providing answers to fundamental questions such as: 1) What happens when a *finite* fraction of nodes experiences a dynamical overload on a single network? 2) How can the failure process caused by dynamical perturbations and interdependence be properly characterized? 3) Which factors determine the cascade to be a second- or a first-order phase transition? 4) What are the *universal properties* that are common to the spreading of cascading failures for different dynamical systems, dependence strengths, and network structures?

## Results

### Cascade Size in Single Networks.

We start by considering the case of a fraction of nodes being perturbed in a graph. Here, each node **1** can be mapped exactly into several dynamical models (Table 1 and *SI Appendix*), such as epidemic processes (where

In the absence of perturbations, each node i of a pristine network reaches its asymptotic steady state

In ref. 39, it was shown that the cascade size *SI Appendix*) follows**3**] on single ErdÖs-Rényi (ER) networks. The results are in good agreement with simulations, as shown in Fig. 1. Notice that, for *SI Appendix* for details) as

### Interdependent Graphs.

Let us now move from isolated to interdependent networks (46⇓⇓⇓–50), and let us consider 2 networks, A and B (having, respectively,

### Failures with the E, B, B D , and R Dynamics.

We now specialize to the case in which the interacting graphs A and B are hosting the dynamical models of Table 1. The nodes of network

When an infinitesimally small fraction **3**, the remaining fraction of nodes in B is

As compared with conclusions in refs. 15 and 22, what is striking here is the *universality* of the failure condition formula (our results in the case of no dynamical behavior are in full agreement with those of ref. 22; Fig. 3*A*), which entitles us to explore a very rich variety of dynamical models, networks’ topologies, and interdependence strengths (results are reported in Fig. 3 *B–F*, as well as in *SI Appendix*).

### First- and Second-Order Transitions.

According to the definition of **4** and **6**, these relationships can be solved with respect to

Taking the *A*), interdependent networks (black line) are more vulnerable, and first-order phase transitions occur more often. In Fig. 4 *B* and *D*, one notices that the critical point decreases as the network connectivity and threshold value are increased, which means that enabling the occurrence of first-order transitions here requires disturbing more nodes or increasing the number of interdependent nodes in the networks. Fig. 4*C* reports that the increase of *SI Appendix*. The threshold value for failure spreading condition accelerates the change from the continuous failure mode (green regions) to abrupt failures (orange regions). Meanwhile, even with weak coupling strengths, the dynamic processes may lead to a first-order percolation transition.

## Discussion

In this work, we have presented a generic theory of failure spreading for randomly connected graphs with arbitrary degree distributions, able to give quantitative predictions on the transition points to percolation.

Our findings show that the interdependent network within dynamical behavior always accelerates the cascading process. In other words, interdependent networks are more vulnerable, and first-order phase transitions occur more often when dynamical behaviors are considered. In particular, when the tolerance coefficient is large enough, our results are in full agreement with the case of no-dynamical-behavior. Due to its general applicability, our theory entitles us to explore a very rich variety of dynamical models and interdependence strengths. *SI Appendix* contains further analytical and numerical results on different dynamical models and different topological structures of the graphs. It is there shown that the first- and second-order phase transitions occur indeed not only in ER networks, but also for scale-free networks with the same dynamical models E, B,

## Materials and Methods

### Generating Functions.

In order to estimate the giant component caused by a cascading failure, the role of the pristine graph’s topological structure needs investigation. Starting from a portion **3**), so the random variable ξ satisfies

### Theoretical Analysis of Critical Conditions.

Let us now specify our approach for the case of 2 coupled ER networks, for which we suppose a Poisson degree distribution and average degrees **4** become **6**, one obtains

The first (second) of the above equations can be solved with respect to

The solutions of Eqs. **7** are either **7**, one finds the 3 unknowns

The condition, instead, for the system featuring a second-order phase transition (where the size of the giant component smoothly decreases to zero) is**7**, one finds

So far, we have shown that, if both conditions of Eqs. **8** and **9** hold, one can obtain the critical point at which the system-failure process changes from a second- to a first-order percolation transition. Adding to Eqs. **7** the first-order condition of Eq. **8** and the second-order condition

## Acknowledgments

This work was supported by National Natural Science Foundation of China Projects U1803263, 71401178, 71771186, and 71631001; National 1000 Young Talent Plan W099102; China Postdoctoral Science Foundation Project n.2017M613336; and Natural Science Foundation of Shaanxi Province Project n.2017JM7011. J.G. was partially supported by Knowledge and Innovation Program Grant 1415291092 at Rensselaer Polytechnic Institute and Office of Naval Research (ONR) Contract N00014-15-1-2640; S.H. acknowledges financial support from the Israel Science Foundation (ISF), ONR Grant N62909-14-1-N019, Defense Threat Reduction Agency (DTRA) Grant HDTRA-1-10-1-0014, BSF-NSF 2015781, Israel Ministry of Science and Technology with the Italian Ministry of Foreign Affairs and the Army Research Office; H.E.S. acknowledges the support from NSF Grant PHY-1505000 and DTRA Grant HDTRA1-14-1-0017 for the Boston University Center for Polymer Studies. We also thank Xueming Liu for useful discussions.

## Footnotes

↵

^{1}D.D. and C.L. contributed equally to this work.- ↵
^{2}To whom correspondence may be addressed. Email: sisb{at}nwpu.edu.cn, zhenwang0{at}gmail.com, or hes{at}bu.edu.

Author contributions: D.D., C.L., S.S., Z.W., D.L., J.G., and S.B. designed research; D.D., C.L., S.S., Z.W., J.G., and S.B. performed research; D.D., C.L., S.S., Z.W., J.G., S.H., H.E.S., and S.B. analyzed data; and D.D., C.L., S.S., Z.W., J.G., S.H., H.E.S., and S.B. wrote the paper.

Reviewers: S.F., Indiana University Bloomington; and V.L., Queen Mary University of London.

The authors declare no competing interest.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1904421116/-/DCSupplemental.

Published under the PNAS license.

## References

- ↵
- ↵
- A. L. Barabási,
- R. Albert

- ↵
- P. Rombach,
- M. A. Porter,
- J. H. Fowler,
- P. J. Mucha

- ↵
- S. Pilosof,
- M. A. Porter,
- M. Pascual,
- S. Kéfi

- ↵
- ↵
- ↵
- S. Boccaletti,
- V. Latora,
- Y. Moreno,
- M. Chavezf,
- D. U. Hwang

- ↵
- ↵
- F. Hu,
- H. Y. Chi,
- S. Yang,
- W. Wang,
- A. Zeng

- ↵
- ↵
- G. Bianconi

- ↵
- ↵
- ↵
- A. E. Motter,
- Y. C. Lai

- ↵
- ↵
- D. F. Klosik,
- A. Grimbs,
- S. Bornholdt,
- M. T. Hutt

- ↵
- Y. Yu et al.

- ↵
- ↵
- S. Boccaletti et al.

- ↵
- ↵
- C. D. Brummitt,
- R. M. DSouza,
- E. A. Leicht

- ↵
- ↵
- ↵
- R. Parshani,
- S. V. Buldyrev,
- S. Havlin

- ↵
- ↵
- ↵
- ↵
- D. Zhou et al.

- ↵
- F. Radicchi

- ↵
- X. Liu,
- H. E. Stanley,
- J. Gao

- ↵
- D. J. Watts

- ↵
- ↵
- ↵
- ↵
- ↵
- A. Barrat,
- M. Barthelemy,
- A. Vespignani

- ↵
- P. Holme,
- J. Saramäki

- ↵
- J. Zhao,
- D. Li,
- H. Sanhedrai,
- R. Cohen,
- S. Havlin

- ↵
- ↵
- B. Schafer,
- D. Witthaut,
- M. Timme,
- V. Latora

- ↵
- ↵
- ↵
- E. O. Voit

- ↵
- C. W. Gardiner

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- M. De Domenico,
- C. Granell,
- M. Porter,
- A. Alex

- ↵
- M. M. Danziger,
- I. Bonamassa,
- S. Boccaletti,
- S. Havlin

## Citation Manager Formats

## Article Classifications

- Physical Sciences
- Applied Physical Sciences