Robustness of a network formed by $n$ interdependent networks with a one-to-one correspondence of dependent nodes

Many real-world networks interact with and depend upon other networks. We develop an analytical framework for studying a network formed by $n$ fully interdependent randomly connected networks, each composed of the same number of nodes $N$. The dependency links connecting nodes from different networks establish a unique one-to-one correspondence between the nodes of one network and the nodes of the other network. We study the dynamics of the cascades of failures in such a network of networks (NON) caused by a random initial attack on one of the networks, after which a fraction $p$ of its nodes survives. We find for the fully interdependent loopless NON that the final state of the NON does not depend on the dynamics of the cascades but is determined by a uniquely defined mutual giant component of the NON, which generalizes both the giant component of regular percolation of a single network ($n=1$) and the recently studied case of the mutual giant component of two interdependent networks ($n=2$). We also find that the mutual giant component does not depend on the topology of the NON and express it in terms of generating functions of the degree distributions of the network. Our results show that, for any $n⩾2$ there exists a critical $p=p_c>0$ below which the mutual giant component abruptly collapses from a finite nonzero value for $p⩾p_c$ to zero for $p<p_c$, as in a first-order phase transition. This behavior holds even for scale-free networks where $p_c=0$ for $n=1$. We show that, if at least one of the networks in the NON has isolated or singly connected nodes, the NON completely disintegrates for sufficiently large $n$ even if $p=1$. In contrast, in the absence of such nodes, the NON survives for any $n$ for sufficiently large $p$. We illustrate this behavior by comparing two exactly solvable examples of NONs composed of Erdős-Rényi (ER) and random regular (RR) networks. We find that the robustness of $n$ coupled RR networks of degree $k$ is dramatically higher compared to the $n$-coupled ER networks of the same average degree $\overline{k}=k$. While for ER NONs there exists a critical minimum average degree $\overline{k}={\overline{k}}_{\min }\sim \ln n$ below which the system collapses, for RR NONs $k_{\min }=2$ for any $n$ (i.e., for any $k>2$, a RR NON is stable for any $n$ with $p_c<1$). This results arises from the critical role played by singly connected nodes which exist in an ER NON and enhance the cascading failures, but do not exist in a RR NON.

Figure 1

Three types of loopless NONs, each composed of five coupled networks. They all have the same percolation threshold and the same giant percolation component.

Figure 2

Dynamics of cascading failures at different time stages. In this figure, each node represents a network. The arrow (on the link) illustrates the direction of damage spreading from the root network to the whole NON shell by shell.

Figure 3

How does the damage spread in a NON system? In this figure, each node represents a network. When looking at network 12 for example, it becomes damaged at $t=2k+1$ ($k=1,2,3,...$). It receives the damage from network 8 at $t=2k+3$, because network 8 gets damage at $t=2$ for the first time and its damage spreads to network 12 at $t=5$ for the first time. This agrees with Eqs. (23) and (22) that network $i$ receives damage from network $j$ if and only if $t-D_{ij}⩾D_{1j}$.

Figure 4

(a) Simulation results of giant component of root network ${\mu }_{t,1}$ after $t$ cascading failures for three types of NON composed of the 5 ER networks shown in Fig. 2. For each network in the NON, $N=100000$ and $\overline{k}=5$. The chosen value of $p$ is $p=0.85$, and the predicted threshold is $p_c=0.76449$ [from Eqs. (44) and (47)]. All points are the results of averaging over 40 realizations. Note that while the dynamics is different for the three topologies, the final $P_{\infty }\equiv {\mu }_{\infty ,1}$ is the same (i.e., the final $P_{\infty }$ does not depend on the topology of the NON). (b) Simulations of the giant component, ${\mu }_{t,1}$, for the tree-like NON (Fig. 2) with the same parameters as in (a) but for $p=0.755<p_c=0.76449$. The figure shows 50 simulated realizations of the giant component left after $t$ stages of the cascading failures compared with the theoretical prediction of Eqs. (8), (22), and (23).

Figure 5

(a) Simulation results for giant component of root network ${\mu }_{t,1}$ after $t$ cascading failures for three types of NON composed of 5 RR networks. The structures of the NON are as shown in Fig. 2. For each network in the NON, $N=100000$ and $k=5$. The chosen value of $p$ is $p=0.65$, and the predicated threshold $p_c=0.6047$ [from Eqs. (58) and (62)]. The points are the results of averaging over 40 realizations. It is seen that, while the dynamics is different for the three topologies, the final $P_{\infty }\equiv {\mu }_{\infty ,1}$ is the same (i.e., the final $P_{\infty }$ does not depend on the topology of the NON). (b) Simulation results of the giant component of the root network ${\mu }_{t,1}$ after $t$ cascading failures for tree-like NON composed of the 5 SF networks shown in Fig. 2. For each network in the NON, $N=100000$, $\lambda =2.3$, and $m=2$. The value of $p$ chosen is $p=0.875$ (below $p_c$). The figure shows 50 simulated realizations of the giant component left after $t$ stages of the cascading failures compared with the theoretical prediction of Eqs. (65), (22) and (23).

Figure 6

Loopless NON is composed of (a) ER networks, (b) RR networks, and (c) SF networks. Plotted is $P_{\infty }$ as a function of $p$ for $k=5$ (for ER and RR networks) and $\lambda =2.3$ for SF networks and several values of $n$. The results obtained using Eq. (43) for ER networks, Eq. (60) for RR networks, and Eq. (65) for SF networks, agree well with simulations.

Figure 7

Loopless NON is composed of (a) ER networks, (b) RR networks, and (c) SF networks. Plotted is $P_{\infty }$ as a function of $p$ for $n=5$ for several values of $\overline{k}$ (ER networks), $k$ (RR networks), and several values of $m$ (SF networks for $\lambda =2.3$). The results obtained using Eq. (43) for ER networks, Eq. (60) for RR networks, and Eq. (65) for SF networks, agree well with simulations.

Figure 8

Critical fraction $p_c$ for different $k$ and $n$ for (a) an ER NON system and (b) a RR NON system. The results for the ER NON system are obtained from Eqs. (44) and (47), while the results of the RR NON system are obtained from the solution of Eqs. (58) and (62). The results are in good agreement with simulations. In the simulations $p_c$ was calculated from the number of cascading failures which diverge at $p_c$ [39] (see also Fig. 10).

Figure 9

For a loopless network of $n$ ER networks, (a) ${\overline{k}}_1{p}_c$ and (b) ${\overline{k}}_1{P}_{\infty }$ as function of the ratio ${\overline{k}}_1/{\overline{k}}_2$ for $n=2$ (dashed), $n=3$ (dotted), $n=4$ (dashed dotted), and $n=5$ (solid) and for $s=1$ ($\circ$), $s=2$ ($\square$), $s=3$ ($\diamond$), and $s=4$ ($▹$), where $s$ denotes the number of individual networks whose average degree are the same ${\overline{k}}_2$ and average degree of the other $n-s$ networks are ${\overline{k}}_1$. The results are obtained using Eqs. (38), (47), (48), and (53).

Figure 10

For a star-like network of 5 ER networks, the average convergence stage $\langle \tau \rangle$ is plotted as a function of $p$ for different $\overline{k}$. In the simulations $N={10}^6$, and averages are obtained from 30 realizations. This feature enables us to find an accurate estimate for $p_c$ in simulations [39].

Figure 11

For the RR NON, $1/p$ as a function of $z$ for different values of $k$ and $n$. All the lines are produced using Eq. (56). The symbols $\diamond$, $\circ$, and $\square$ show for $k=5$ the critical solutions for $n=1$, $n=2$, and $n=5$ respectively. These critical thresholds coincide with the results in Fig. 7b. The dashed-dotted line shows that, when $k=2$, the function (56) has only a trivial solution $z=0$ for $p=1$.

Figure 12

For the SF NON, $1/p$ as a function of $z$ (a) for different values of $\lambda$ when $n=2$ and $m=1$, (b) for different values of $n$ when $\lambda =2.4$ and $m=2$. All the lines are produced from the $R_{i,i,n}\left(z\right)$ function, Eq. (68). (a) The symbols $\circ$ and $\diamond$ show the physical solutions for $\lambda =2.2$ and $\lambda =2.3$ respectively when $p=0.95$. The symbols $\square$ and $▹$ show the critical solutions $(z_c,p_c)$ for $\lambda =2.2$ and $\lambda =2.3$ when $p=p_c$. (b) The symbol $\circ$ shows the physical solution for $n=3$, $p=0.8$. The critical solutions $(z_c,p_c)$ are shown as $n=7$, ($\diamond$), $n=5$ ($\square$), and $n=3$ ($▹$).