Cascade of failures in coupled network systems with multiple support-dependence relations

We study, both analytically and numerically, the cascade of failures in two coupled network systems A and B, where multiple support-dependence relations are randomly built between nodes of networks A and B. In our model we assume that each node in one network can function only if it has at least a single support link connecting it to a functional node in the other network. We assume that networks A and B have (i) sizes $N^A$ and $N^B$, (ii) degree distributions of connectivity links $P^A(k)$ and $P^B(k)$, (iii) degree distributions of support links ${\mathrm{P̃}}^A(k)$ and ${\mathrm{P̃}}^B(k)$, and (iv) random attack removes $(1-R^A)N^A$ and $(1-R^B)N^B$ nodes form the networks A and B, respectively. We find the fractions of nodes ${\mu }_{\infty }^A$ and ${\mu }_{\infty }^B$ which remain functional (giant component) at the end of the cascade process in networks A and B in terms of the generating functions of the degree distributions of their connectivity and support links. In a special case of Erdős-Rényi networks with average degrees $a$ and $b$ in networks A and B, respectively, and Poisson distributions of support links with average degrees $\mathrm{ã}$ and $\mathrm{b̃}$ in networks A and B, respectively, ${\mu }_{\infty }^A=R^A[1-\exp (-\mathrm{ã}{\mu }_{\infty }^B)][1-\exp (-a{\mu }_{\infty }^A)]$ and ${\mu }_{\infty }^B=R^B[1-\exp (-\mathrm{b̃}{\mu }_{\infty }^A)][1-\exp (-b{\mu }_{\infty }^B)]$. In the limit of $\mathrm{ã}\to \infty$ and $\mathrm{b̃}\to \infty$, both networks become independent, and our model becomes equivalent to a random attack on a single Erdős-Rényi network. We also test our theory on two coupled scale-free networks, and find good agreement with the simulations.

Figure 1

Demonstration of the stages of the cascade of failures in coupled networks A and B of size $N^A=N^B=7$. Curves represent connectivity links within the network, while arrows (directed links) represent the support links connecting a support node in one network to the dependent node in the other network. Among the total 12 directed links, half of them $\mathrm{ã}{N}^A=6$ represent the support from nodes in network B to nodes in network A (arrows from nodes in network B to nodes in network A). The rest $\mathrm{b̃}{N}^B=6$ links represent the support from nodes in network A to nodes in network B. The support-dependence relations between nodes in network A and network B are random. Initially, the attack is on node $A_1$ (shown in red) in network A and node $B_6$ (shown in red) in network B. The failed nodes are removed from the plot. In the first stage of the cascade of failures in network A, $A_1$ fails because of removal, node $A_7$ fails because of it has no support links, $A_2$ and $A_6$ fail because of separation from the giant component of network A. All the failed nodes will lead to failures of support links starting from them. Since we assume that the attack on network A occurs before that on network B, the support link from $B_6$ to $A_5$ is considered to be functional. In the first stage of the cascade of failures in network B, we first remove support links connecting network B to non-giant-component nodes in network A ($B_3$ to $A_1$, $B_2$ to $A_2$, $B_7$ to $A_6$). Next, node $B_6$ fails because of the attack and nodes $B_1$, $B_2$ and $B_7$ also fail because of no support. $B_3$ fails because it becomes separated from the giant component (nodes $B_4$ and $B_5$) of network B. Finally, after removing support links connecting nodes in network A to non-giant-component nodes in network B ($A_3$ to $B_3$, $A_4$ to $B_3$ and $A_5$ to $B_6$), the coupled network system reaches a stable state after one step in the cascade of failures, since all nodes in both giant components are connected and each node have at least one support node from the other network.

Figure 2

Demonstration of the functional relation between ${\mu }_{\infty }^B$ and ${\mu }_{\infty }^A$ in Eqs. (19) and (20) for a system of two coupled ER networks with $a=b=4$, $\mathrm{b̃}=\mathrm{ã}=4$, and $R^B=1$ at different values of $R^A$. Since we use $R^B=1$, at different $R^A$, the relation between ${\mu }_{\infty }^B$ and ${\mu }_{\infty }^A$ given by Eq. (20) remains the same (shown by the dashed line). Equation (19) with $R^A=0.6$, 0.43, and 0.4 is shown. One can see that when $R^A<0.43$, only a trivial solution $({\mu }_{\infty }^A=0,{\mu }_{\infty }^B=0)$ exists for Eqs. (19) and (20). The value $1-R_c^A\equiv 1-0.43=0.57$ represents the maximum fraction of nodes in network A one can randomly remove at the initial stage of the cascade of failures for which the non-zero giant components of both networks still exist at the stable state. The abrupt disappearance of the nontrivial solution at $R^A<R_c^A$ corresponding to complete fragmentation of both networks represents the first order nature of the percolation phase transition for coupled networks.

Figure 3

The case of coupled ER networks. Comparison between the theoretical predictions, obtained from Eqs. (12), (15), (11), and (18), and numerical simulations with $N^A=N^B={10}^6$, $a=b=4$, $\mathrm{b̃}=\mathrm{ã}=4$, $R^B=1$, and several values of $R^A$. (a) and (b) show ${\mu }_n^A$ and ${\mu }_n^B$ at different stages $n$ of the cascade of failures for $R^A=0.7$ and $R^A=0.6>R_c^A\approx 0.43$ for both theory (lines) and simulations (symbols). One can see that both ${\mu }_n^A$ and ${\mu }_n^B$ approach a stable value ${\mu }_{\infty }^A$ and ${\mu }_{\infty }^B$ at the end of the cascade of failures. The agreement between theory and numerical simulations is very good. (c) and (d) show ${\mu }_n^A$ and ${\mu }_n^B$ at different stages $n$ of the cascade of failures for $R^A\approx R_c^A$. The bare lines represent several realizations of the simulations and the lines with symbols represent the theoretical predictions. One can see that for the early stages (small $n$) the agreement is good, however at large $n$ the deviation due to random fluctuations in the actual fraction of the giant component starts to increase. The random realizations split into two classes: one that converges to a non-zero giant component for both networks and the other that results in a complete fragmentation.

Figure 4

The case of coupled SF networks. Comparison between the theoretical predictions, obtained from Eqs. (12), (9), (10), and (18), and numerical simulations with $N^A=N^B={10}^6$, ${\lambda }^A={\lambda }^B=2.5$, $\mathrm{b̃}=\mathrm{ã}=4$, $R^B=1$, and different values of $R^A$. (a) and (b) show ${\mu }_n^A$ and ${\mu }_n^B$ at different stages $n$ of the cascade of failures for $R^A=0.7$ and $R^A=0.6>R_c^A\approx 0.385$ for both theory (lines) and simulations (symbols). Similar to Fig. 3, one can see that both ${\mu }_n^A$ and ${\mu }_n^B$ approach a stable value ${\mu }_{\infty }^A$ and ${\mu }_{\infty }^B$ at the end of cascade failures. The agreement between the theory and numerical simulations is very good. (c) and (d) show ${\mu }_n^A$ and ${\mu }_n^B$ at different stages $n$ of the cascade of failures for $R^A\approx R_c^A$. Bare lines represent several realizations of the simulations and the lines with symbols represent the theoretical predictions. One can see that for the early stages the agreement is good, however at large $n$ the deviation due to random fluctuations in the actual fraction of the giant component increase. The random realizations split into two classes: one that converges to a nonzero giant component for both networks and the other that results in a complete fragmentation. For coupled SF networks, at $R^A=R_c^A$, the fluctuations of both ${\mu }_n^A$ and ${\mu }_n^B$ seem to be relatively larger than that of coupled ER networks, due to the existence of large degree nodes in SF networks.

Figure 5

The fraction of the giant components of network (a) A, ${\mu }_{\infty }^A$ and network (b) B, ${\mu }_{\infty }^B$ in the stable states as a function of $R^A$ and $R^B$ for coupled ER networks A and B with $N^A=N^B={10}^6$, $a=b=4$, $\mathrm{b̃}=\mathrm{ã}=4$, and $1-R^A=2(1-R^B)$. Several curves for $\mathrm{b̃}=\mathrm{ã}=4$, $\mathrm{b̃}=\mathrm{ã}=8$, and $\mathrm{b̃}=\mathrm{ã}=32$ are shown. The theory (lines) agrees very well with the simulation results (symbols). One can see that for a given set of $\mathrm{b̃}$ and $\mathrm{ã}$ there exist critical thresholds $R_c^A$ and $R_c^B$, below which both networks will collapse and have no stable nonzero giant components. The value of $R_c^A$ approaches the critical threshold of random percolation ($r=1/a=0.25$) of a single network for large values of $\mathrm{b̃}$ and $\mathrm{ã}$. The initial attack on network B is smaller than that on network A and thus $R_c^B>R_c^A$.

Figure 6

The dependences of (a) $R_c$ and (b) ${\mu }_c$ on $\mathrm{b̃}=\mathrm{ã}$ for coupled ER networks with $N^A=N^B={10}^6$, $a=b=4$, and $1-R^A=2(1-R^B)$. In (a), the critical initial fraction of the network A, $R_c^A$, and the critical initial fraction of the network B, $R_c^B$, are shown as a function of $\mathrm{b̃}=\mathrm{ã}$. The theory (full line and dashed lines) fits well the simulation results (symbols). Note that $R_c^A$ approaches the critical threshold ($1/a$) of random percolation for a single network, as also predicted by Eqs. (19) and (20). In (b), the giant component of both network ${\mu }_c^A$ and ${\mu }_c^B$ are shown as a function of $\mathrm{b̃}=\mathrm{ã}$ at $R_c^A$ and $R_c^B$. The theory (full line and dashed line) fits well the simulation results (symbols). One can see that for large $\mathrm{b̃}=\mathrm{ã}$, ${\mu }_c^A$ and ${\mu }_c^B$ both approach zero as expected for a single network. However, ${\mu }_c^A$ and ${\mu }_c^B$ will never reach zero for finite $\mathrm{b̃}$ and $\mathrm{ã}$ and the phase transition thus remain a first order.