# Eradicating catastrophic collapse in interdependent networks via reinforced nodes

^{a}Center for Polymer Studies, Boston University, Boston, MA 02215;^{b}Department of Physics, Boston University, Boston, MA 02215;^{c}School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China;^{d}School of Mathematics, Southwest Jiaotong University, Chengdu 610031, China;^{e}Big Data Research Center, University of Electronic Science and Technology of China, Chengdu 611731, China;^{f}Minerva Center, Bar-Ilan University, Ramat-Gan 52900, Israel;^{g}Department of Physics, Bar-Ilan University, Ramat-Gan 52900, Israel

See allHide authors and affiliations

Contributed by H. Eugene Stanley, December 29, 2016 (sent for review April 21, 2016; reviewed by Antonio Coniglio and Michael F. Shlesinger)

## Significance

Percolation theory assumes that only the largest connected component is functional. However, in reality, some components that are not connected to the largest component can also function. Here, we generalize the percolation theory by assuming a fraction of reinforced nodes that can function and support their components, although they are disconnected from the largest connected component. We find that the reinforced nodes reduce significantly the cascading failures in interdependent networks system. Moreover, including a small critical fraction of reinforced nodes can avoid abrupt catastrophic failures in such systems.

## Abstract

In interdependent networks, it is usually assumed, based on percolation theory, that nodes become nonfunctional if they lose connection to the network giant component. However, in reality, some nodes, equipped with alternative resources, together with their connected neighbors can still be functioning after disconnected from the giant component. Here, we propose and study a generalized percolation model that introduces a fraction of reinforced nodes in the interdependent networks that can function and support their neighborhood. We analyze, both analytically and via simulations, the order parameter—the functioning component—comprising both the giant component and smaller components that include at least one reinforced node. Remarkably, it is found that, for interdependent networks, we need to reinforce only a small fraction of nodes to prevent abrupt catastrophic collapses. Moreover, we find that the universal upper bound of this fraction is 0.1756 for two interdependent Erdős–Rényi (ER) networks: regular random (RR) networks and scale-free (SF) networks with large average degrees. We also generalize our theory to interdependent networks of networks (NONs). These findings might yield insight for designing resilient interdependent infrastructure networks.

Complex networks often interact and depend on each other to function properly (1⇓⇓⇓⇓⇓⇓–8). Because of interdependencies, these interacting networks may easily suffer abrupt failures and face catastrophic consequences, such as the blackouts of Italy in 2003 and North America in 2008 (3, 4, 6). Thus, a major open challenge arises as how to tackle the vulnerability of interdependent networks. Virtually, many existing theories on the resilience of interacting networks have centered on the formation of the largest cluster (called the giant component) (4, 6, 9⇓⇓⇓⇓⇓–15) and consider only the nodes in the giant component as functional, because all of the small clusters do not have a connection to the majority of nodes, which are in the giant component.

However, in many realistic networks, in case of network component failures, some nodes (which we call here reinforced nodes) and even clusters containing reinforced nodes outside of the giant component can resort to contingency mechanisms or backup facilities to keep themselves functioning normally (16⇓–18). For example, small neighborhoods in a city, when facing a sudden power outage, could use alternative facilities to sustain themselves. Consider also the case where some important internet ports, after their fiber links are cutoff from the giant component, could use satellites (19) or high-altitude platforms (20) to exchange vital information. These possibilities strongly motivate us to generalize the percolation theory (9, 21) to include a fraction of reinforced nodes that are capable of securing the functioning of the finite clusters in which they are located. We apply this framework to study a system of interdependent networks and find that a small fraction of reinforced nodes can avoid the catastrophic abrupt collapse.

In this paper, we develop a mathematical framework based on percolation (4, 6, 12, 13, 22) for studying interdependent networks with reinforced nodes and find exact solutions to the minimal fraction of reinforced nodes needed to eradicate catastrophic collapses. In particular, we apply our framework to study and compare three types of random networks: (*i*) Erdős–Rényi (ER) networks with a Poisson degree distribution [*ii*) scale-free (SF) networks with a power law degree distribution [*iii*) regular random (RR) networks with a Kronecker delta degree distribution [

## Model

Formally, for simplicity and without loss of generality, our model consists of two networks,

We introduce the generating function of the degree distribution *SI Text*, section 2):

Accordingly, the sizes of the functioning components are determined by (*SI Text*, section 2)

## Results

For a general system of interdependent networks **1**–**5**. As an example, Fig. 2 shows the excellent agreement between simulation and theory.

However, it is important to find analytic expressions for **1** and **2** to a single equation. Similarly, it renders **5** to **1**–**5**, we derive *SI Text*, section 3).

Surprisingly, we find that, even for a system built with a relatively high dependency coupling, there exists a specific value *SI Text*, section 3). Therefore, *SI Text*, section 3)*A* and *B* depicts the dramatic behavior change of the functioning components as *C* shows that *D* that the jump of the functioning component

We next solve this critical value *SI Text*, section 3)**7**, **7** for

Hence, for any **7**; then, *SI Text*, section 3)*SI Text*, section 3.1.1) (25). Similar scaling behaviors have been reported in a bootstrap percolation problem (29) and a Fredrickson–Andersen model on Bethe lattice with quenched impurities (38, 39).

In Fig. 4*A*, we plot **7** as a function *B*, we plot

Similarly, we obtain *A*) and *B*). Note that, as *SI Text*, section 3.2). For RR networks, as *SI Text*, section 3.2).

Next, we solve *SI Text*, section 4.1). We find that, in two ER networks, as *B*). Moreover, in the case of SF networks when *SI Text*, section 4.2).

Our approach can be generalized to solve the case of tree-like networks of networks (NONs) (6, 34). For example, we study the symmetric case of an ER NON with *SI Text*, section 3.1.2). This relationship indicates that the bigger

## Test on Empirical Data

We next test our mathematical framework on an empirical network, the US power grid (PG) (40), with the introduction of a small fraction of reinforced nodes. It is difficult to establish the exact structure of the network that the PG interacts with and their interdependencies because of lack of data. However, to get qualitative insight into the problem, we couple the PG with either ER or SF network, which can be regarded as approximations to many real world networks. Our motivation is to test how our model performs in the interdependent networks system with some real world network features. Note that, here, our results present cascading failures caused by structural failures and do not represent failures caused by real dynamics, such as cascading failures caused by overloads, that appear in a PG network system. Fig. 6 compares the mutual percolation of two systems of interdependent networks with the same interdependence strength: PG coupled to a same-sized ER network (Fig. 6*A*) and PG coupled to a same-sized SF network (Fig. 6*B*). As discussed above, for *B*).

## Summary

In summary, we have developed a general percolation framework for studying interdependent networks by introducing a fraction of reinforced nodes at random. We show that the introduction of a relatively small fraction of reinforced nodes,

## SI Text

### 1. Probabilistic Framework for Single Networks with Reinforced Nodes.

For a single random network

Suppose we randomly choose a link in network

There is a probability **S15**, **S29**, and **S32**–**S35** for

Therefore, for a randomly chosen node *i*) it is a reinforced node, or (*ii*) it is not a reinforced node, but at least one of its

Furthermore, in the network percolation problem, when a fraction **S33** and **S35** of **S2** become

Similarly, the probability that a randomly chosen node is in the functioning component (14, 29⇓⇓⇓–33) is

Among the functioning component, the biggest contributor is the giant component, which depends on the network structure and bears no influence from reinforced nodes. Thus, we denote by

We tested our theory on single random networks by simulations as shown in Fig. S2 with two types of networks: ER and SF. Simulation results agree well with theoretical predictions as shown in Fig. S2. Note that, for ER network, the giant component undergoes a second-order phase transition at

### 2. Probabilistic Framework for Interdependent Networks with Reinforced Nodes.

For a system of two interdependent networks *A*) or dependent on a single node *B*). Thus, this random link leads to the functioning component of network *A*) belongs to the functioning component of network *A*) belongs to the functioning component of network **S8** and **S9** into Eq. **S10**, we obtain

Similarly, we would obtain the probability that a randomly chosen link in

Accordingly, a randomly chosen node

Hence, the probability corresponding to **S13** and **S14** into Eq. **S15**, we obtain

Analogously, for network

When we randomly remove a fraction

Finally, we arrive at the equation for

Like in a single network, here, we denote **S18**,

If the system has an abrupt phase transition at

We test our theory with a system of interdependent ER and SF networks as shown in Fig. S4. Note that simulation results agree well with theoretical predictions, and when the giant components undergo a first-order phase transition at

Hence, Eqs. **S18**–**S22** serve as the general framework of the text.

### 3. Solving Interdependent Networks with Symmetry.

In the symmetric case where **S24**, we have**S23** as

Therefore, we can combine Eqs. **S25** and **S26** to solve for

As shown in Fig. S5, for **S26** with respect to **S24**, we know that **S27** could be reduced to**S25**, we can further transform the determinant into the following form:**S30** will be extensively used to obtain

#### 3.1. ER networks.

For ER networks, we have **S30**, we can explicitly solve

Apart from the mathematical argument for the existence of the special value

Note that

##### 3.1.1. Critical exponent near criticality.

For a system of two interdependent ER networks with built-in symmetry, according to Eq. **S23**,

Moreover, at the critical point, the derivatives of both sides of Eq. **S36** with respect to

Plugging **S43**, after some simplification, we would obtain**S42** and **S44**, we can conclude that **S32**. We further calculate the value of

Therefore, if *A*, the scaling behavior of the functioning component near the first-order transition is characterized by the critical exponent *B*, the scaling behavior of the functioning component near the first-order transition is characterized by the critical exponent

##### 3.1.2. NONs.

Our approach can be generalized to solve the case of loopless NONs (6, 42) with the built-in symmetry, where every member network has the same average degree **S23**,

We tested our theory on a tree-like fully interdependent ER NON system with several values of *A*. For an ER NON, we can also get a boundary separating the first-order transition regime and the no transition regime. Especially, here, for *B*. For any

#### 3.2. Fully interdependent RR and SF networks with symmetry.

For **S30** to numerically solve *B* for SF networks. Here, we are mainly interested in **S23**, we readily find out that**S30** is reduced to**S23**:

Thus, Eqs. **S50** and **S51** jointly determine

##### 3.2.1. RR networks.

For RR networks, we have **S50** and **S51** that **S51** first, we get **S50**, we obtain the equation of **S52**, we obtain *B*.

For **S54** into Eq. **S55** and get the value of **S54** to get *B*. However, we are also interested in getting the asymptotic form of **S54** reduces to**S56**, we can reduce Eq. **S55** to**S57**, as **S57**, we would have**S56**, we would have

##### 3.2.2. SF networks.

For SF network, the degree distribution is **S50** and **S51**, we can get *A*.

Moreover, when

### 4. Solving Fully Interdependent Networks Without Symmetry.

#### 4.1. ER networks.

We start with ER networks, because the associated generating functions have the nice property of **S18** with **S66** into Eq. **S65**, we can get**S67** indicates that, for the same set of

Next, we introduce a variable **S67** as a single transcendental equation of **S66** recast as a function of

Hence, getting **S68** and substituting it into Eq. **S69**, we obtain the value of

Now, we want to derive **S68** with respect to

(*i*) Note that, in our derivation of *ii*) Also note that, if we interchange **S71**, we get the expression exactly unchanged, which means that**S74** essentially means

Fig. S9 shows the existence of

We next solve the dependence of *B*). Hence, for any system of interdependent ER networks, we can conclude that

#### 4.2. RR and SF networks.

Now we turn to RR and SF networks where their associated generating functions satisfy **S75** into **S22**, we would have**S75** and **S77** jointly determine the phase transition point for any fully interdependent random networks.

In the case of **S77** into Eq. **S75** to obtain an equation set for

Notice that Eq. **S78** is the self-consistent equation set for **S78**, because for example, two fully interdependent networks always suffer abrupt collapse under random node removals. However, when **S78** will suddenly disappear. This scenario corresponds to the case where**S76** and **S79**, we obtain the determinant that

According to Eq. **S80**, *A*, where *SI Text*, *Solving Interdependent Networks with Symmetry*. Similarly, from Eq. **S80**, *B*, where

## Acknowledgments

We thank the financial support of the Office of Naval Research Grants N00014-09-1-0380, N00014-12-1-0548, N62909-16-1-2170, and N62909-14-1-N019; Defense Threat Reduction Agency Grants HDTRA-1-10-1-0014 and HDTRA-1-09-1-0035; National Science Foundation Grants PHY-1505000, CHE-1213217, and CMMI 1125290; Department of Energy Contract DE-AC07-05Id14517; and US–Israel Binational Science Foundation–National Science Foundation Grant 2015781. Y.H. is supported by National Natural Science Foundation of China Grant 61203156, the Hundred-Talent Program of the Sun Yat-sen University, and the Chinese Fundamental Research Funds for the Central Universities Grant 16lgjc84. Financial support was also provided by the European Multiplex and Dynamics and Coevolution in Multilevel Strategic Interaction Games (CONGAS) Projects; the Israel Ministry of Science and Technology with the Italy Ministry of Foreign Affairs; the Next Generation Infrastructure (Bsik); and the Israel Science Foundation. We also thank the Forecasting Financial Crises (FOC) Program of the European Union for support.

## Footnotes

- ↵
^{1}To whom correspondence may be addressed. Email: hes{at}bu.edu or yanqing.hu.sc{at}gmail.com.

Author contributions: X.Y., Y.H., and S.H. designed research; X.Y. and Y.H. performed research; S.H. contributed new reagents/analytic tools; X.Y., H.E.S., and S.H. analyzed data; and X.Y., Y.H., H.E.S., and S.H. wrote the paper.

Reviewers: A.C., University of Naples; and M.F.S., Office of Naval Research.

The authors declare no conflict of interest.

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

## References

- ↵.
- Rinaldi SM,
- Peerenboom JP,
- Kelly TK

- ↵.
- Little RG

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵.
- Onnela J-P, et al.

- ↵.
- Coniglio A

- ↵.
- Radicchi F

- ↵
- ↵
- ↵
- ↵.
- Newman ME

- ↵.
- Cohen R,
- Havlin S

- ↵.
- Jenkins N

- ↵
- ↵.
- Alanne K,
- Saari A

- ↵.
- Henderson TR,
- Katz RH

- ↵.
- Mohammed A,
- Mehmood A,
- Pavlidou F-N,
- Mohorcic M

- ↵.
- Vicsek T,
- Shlesinger MF,
- Matsushita M

- ↵.
- Brown A,
- Edelman A,
- Rocks J,
- Coniglio A,
- Swendsen RH

- ↵.
- Bollobás B

- ↵
- ↵
- ↵.
- Hu Y,
- Ksherim B,
- Cohen R,
- Havlin S

- ↵.
- Hu Y, et al.

- ↵
- ↵.
- Baxter GJ,
- Dorogovtsev SN,
- Goltsev AV,
- Mendes JFF

- ↵.
- Baxter GJ,
- Dorogovtsev SN,
- Mendes JFF,
- Cellai D

- ↵.
- Min B,
- Goh K-I

- ↵
- ↵.
- Min B,
- Lee S,
- Lee K-M,
- Goh K-I

- ↵.
- Bianconi G,
- Dorogovtsev SN

- ↵.
- Gao J, et al.

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

- ↵.
- Ikeda H,
- Miyazaki K

- ↵.
- de Candia A,
- Fierro A,
- Coniglio A

- ↵
- ↵.
- Newman MEJ

- ↵.
- Gao J,
- Buldyrev SV,
- Havlin S,
- Stanley HE

## Citation Manager Formats

## Article Classifications

- Physical Sciences
- Applied Physical Sciences