Percolation of a general network of networks

Percolation theory is an approach to study the vulnerability of a system. We develop an analytical framework and analyze the percolation properties of a network composed of interdependent networks (NetONet). Typically, percolation of a single network shows that the damage in the network due to a failure is a continuous function of the size of the failure, i.e., the fraction of failed nodes. In sharp contrast, in NetONet, due to the cascading failures, the percolation transition may be discontinuous and even a single node failure may lead to an abrupt collapse of the system. We demonstrate our general framework for a NetONet composed of $n$ classic Erdős-Rényi (ER) networks, where each network depends on the same number $m$ of other networks, i.e., for a random regular network (RR) formed of interdependent ER networks. The dependency between nodes of different networks is taken as one-to-one correspondence, i.e., a node in one network can depend only on one node in the other network (no-feedback condition). In contrast to a treelike NetONet in which the size of the largest connected cluster (mutual component) depends on $n$, the loops in the RR NetONet cause the largest connected cluster to depend only on $m$ and the topology of each network but not on $n$. We also analyzed the extremely vulnerable feedback condition of coupling, where the coupling between nodes of different networks is not one-to-one correspondence. In the case of NetONet formed of ER networks, percolation only exhibits two phases, a second order phase transition and collapse, and no first order percolation transition regime is found in the case of the no-feedback condition. In the case of NetONet composed of RR networks, there exists a first order phase transition when the coupling strength $q$ (fraction of interdependency links) is large and a second order phase transition when $q$ is small. Our insight on the resilience of coupled networks might help in designing robust interdependent systems.

Figure 1

Illustration of regular and random regular (RR) NetONet of interdependent random networks. (a) An example of a regular network, a lattice with periodic boundary condition composed of nine interdependent networks represented by nine circles. The degree of the NetONet is $m=4$, i.e., each network depends on four networks. (b) A RR network composed of six interdependent networks represented by six circles. The degree of the NetONet is $m=3$, i.e., each network depends on three networks. The analytical results for the NetONet [Eqs. (15) and (17)] are exact and the same for both cases (a) and (b). (c) Schematic representation of the dependencies of the networks. Circles represent networks in the NetONet, and the arrows represent the partially interdependent pairs. For example, a fraction of $q_{3i}$ of nodes in network $i$ depends on nodes in network 3. Pairs of networks which are not connected by dependency links do not have nodes that directly depend on each other.

Figure 2

(a) Simulation results compared with theory of the giant component of network 1, $P_{1,t}$, after $t$ cascading failures for the lattice NetONet composed of nine ER networks shown in Fig. 1a. For each network in the NetONet, $N={10}^5$, $m=4$, and $\overline{k}=8$, and $q=0.4>q_c\doteq 0.382$ [predicted by Eq. (30)]. The chosen value of $p$ is $p=0.945$, and the predicted threshold is $p_c^I=0.952$ [from Eq. (27)]. (b) Simulations compared to theory of the giant component $P_{1,t}$ for the random regular NetONet composed of six ER networks shown in Fig. 1b with the no-feedback condition. For each network in the NetONet, $N={10}^5$, $m=3$, $\overline{k}=8$, $q=0.49>q_c\doteq 0.4313$ [predicted by Eq. (30)], and for $p=0.866<p_c^I\doteq 0.8696$ [from Eq. (27)]. (c) Simulations compared to theory of the giant component $P_{1,t}$ for the random regular NetONet composed of six ER networks shown in Fig. 1b with the feedback condition. For each network in the NetONet, $N={10}^5$, $m=3$, $\overline{k}=8$, $q=0.4<q_{\max }=0.5$ [predicted by Eq. (50)], and for $p=0.9>p_c\doteq 0.5787$ [from Eq. (48)]. The results are averaged over 20 simulated realizations of the giant component left after $t$ stages of the cascading failures and are compared with the theoretical prediction of Eq. (9).

Figure 3

The giant component for a RR network of ER networks $P_{\infty }$ as a function of $p$, for ER networks with average degree $\overline{k}=10$, (a) for two different values of $m$ and $q=0.5$, (b) for two different values of $q$ and $m=3$. The curves in (a) and (b) are obtained using Eq. (23) and are in excellent agreement with simulations. The points symbols are obtained from simulations by averaging over 20 realizations for $N=2\times {10}^5$. In (a), simulation results are shown as circles ($n=6$) for $m=2$ and as diamonds ($n=12$) for $m=3$. These simulation results support our theoretical result [Eq. (23)], which is indeed independent of the number of networks $n$.

Figure 4

Plot of $R\left(z\right)$ as a function of $z$ for a RR network of ER networks, for different values of $q$ when $m=3$ and $\overline{k}=8$. All the lines are produced using Eq. (24). The symbols, filled circle and filled square, show the critical thresholds $p_c^{II}$ when $q=0.42<q_c=0.4313$ and $p_c^I$ when $q=0.5<q_{\max }=0.5462$. These critical thresholds coincide with the results in Fig. 3a. The dashed dotted line shows that when $q=0.58>q_{\max }$ Eq. (24) has no solution for $p=1$, which corresponds to the case of complete collapse of the NetONet.

Figure 5

The giant component for a RR NetONet formed of ER networks at $p_c$, $P_{\infty }\left(p_c\right)$, as a function of $q$. The curves are (a) for $m=3$ and two different values of $\overline{k}$, and (b) for $\overline{k}=8$ and two different values of $m$. The curves are obtained using Eqs. (23) and (26) and are in excellent agreement with simulations (symbols). Panels (a) and (b) show the location of $q_{\max }$ and $q_c$ for two values of $m$. Between $q_c$ and $q_{\max }$ the transition is first order represented since $P_{\infty }\left(p_c\right)>0$. For $q<q_c$, the transition is second order since $P_{\infty }\left(p_c\right)=0$, and for $q>q_{\max }$, the NetONet collapses [$P_{\infty }\left(p_c\right)=0$] and there is no phase transition ($p_c=1$).

Figure 6

The phase diagram for a RR network of ER networks (a) for $m=3$ and $\overline{k}=8$, (b) for $m=2$ and $\overline{k}=10$. The solid curves show the second order phase transition [predicted by Eq. (26), the left-hand side axis], the dotted curves show the first order phase transition [predicted by Eq. (27), the left-hand side axis], and the dashed-dotted curves show the first order phase phase transition, yielding nonzero $P_{\infty }\left(p_c\right)$ at $q_c$ [predicted by Eq. (30) from zero (at $q_c$) to nonzero values (the right-hand side axis)]. As $m$ decreases and $\overline{k}$ increases, the region for $P_{\infty }>0$ increases, showing a better robustness. The circles show the tricritical point $q_c$, below which second order transition occurs and above which a first order transition occurs. The squares show the critical point $q_{\max }$, above which the NetONet completely collapses even when $p=1$. Note that the case $m=2$ can be realized only if the network of network is a loop like network formed by $n$ interdependent networks or includes several loop like network of networks and the total number of networks is $n$.

Figure 7

For a RR NetONet formed of SF networks $R\left(z\right)$ as a function of $z$ for different values of $q$ when $m=3$, $\lambda =2.3$, $s=2$, and $M=1000$. (i) When $q$ is small ($q=0.4<q_c$), $R\left(z\right)$ is a monotonically increasing function of $z$, and the system shows a second order phase transition. (ii) When $q$ is larger ($q_c<q=0.45<q_{\max }$), $R\left(z\right)$ as a function of $z$ shows a peak at $z_c$ (see inset) which corresponds to a first order phase transition, followed by a second order phase transition which happened because $R\left(z\right)$ increases with $z$ monotonically when $z$ is large enough. The square symbol represents the critical point of the sharp jump ($z_c$). (iii) When $q$ is large enough ($q=0.55>q_{\max }$), $R\left(z\right)$ decreases with $z$ first, and then increases with $z$, which corresponds to the system collapse.

Figure 8

Results for a RR NetONet formed of SF networks. (a) The giant component $P_{\infty }$ as a function of $p$ for different values of $m$ and $q$ for $\lambda =2.5$. (b) The critical threshold $p_c^I$ and (c) the corresponding giant component at the threshold $P_{\infty }\left(p_c^I\right)$ as a function of coupling strength $q$ for $m=2$ and 3. The symbols in (a) represent simulation results, obtained by averaging over 20 realizations for $N=2\times {10}^5$ and number of networks $n=6$ (squares) and $n=4$ (circles). The lines are the theoretical results obtained using Eqs. (17) and (1, 2, 3). We can see in (a) that the system shows a hybrid phase transition for $m=2$ and $q_c<q=0.62<q_{\max }=1/(m-1)$. When $q<q_c$, the system shows a second order phase transition and the critical threshold is $p_c^{II}=0$. However, in the simulation when $p$ is small (but not zero), $P_{\infty }=0$. This happens because $p_c^{II}=0$ is valid only when the network size approaches $N=\infty$ and $M=\infty$, but in simulations we have finite systems. Note that, when $q_c<q<q_{\max }$ the system shows a hybrid transition shown in (a) and (c), and when $q>q_{\max }$, all the networks collapse even if one node fails. We call this hybrid transition because $P_{\infty }^{-}>0$, which is different from the case of ER networks with first order phase transition where $P_{\infty }^{-}=0$.

Figure 9

The giant component for a RR network of ER networks with feedback condition $P_{\infty }$ as a function of $p$ for ER average average degree $\overline{k}=10$, for different values of $m$ for $q=0.5$ (a) and for different values of $q$ for $m=3$ (b). The curves in (a) and (b) are obtained using Eq. (44) and are in excellent agreement with simulations. The symbols are obtained from simulations of Fig. 1b topology when $m=3$ and $n=6$ networks (forming a circle when $m=2$) by averaging over 20 realizations of $N=2\times {10}^5$. The absence of first order regime in NetONet formed of ER networks is due to the fact that at the initial stage, nodes in each network are interdependent on isolated nodes (or clusters) in the other network. However, if only nodes in the giant components of both networks are interdependent, all three regimes (second order, first order, and collapse) will occur, as in the case of a RR NetONet formed of RR networks [see Eq. (50) and Fig. 12].

Figure 10

(a) Comparison of $p_c$ as a function of $q$ between no-feedback and feedback conditions when $\overline{k}=10$. For the no-feedback condition, the parts of curves below the symbols show $p_c^{II}$ and above the symbols show $p_c^I$. For the feedback condition, they only have the $p_c$ of second order, and $p_c^{II}$ for the no-feedback case is equal to $p_c$ of the feedback case, but this does not mean that these two cases have equal vulnerability. $P_{\infty }\left(1\right)$ as a function of $q$ for different values of $m$ when $\overline{k}=8$ with (b) no-feedback condition and (c) feedback condition. When $q=0$, $P_{\infty }\left(1\right)=1-\text{exp}(-\overline{k})$ for all $m$ and for both feedback and no-feedback cases. Comparing (b) and (c), we can see that the feedback case is much more vulnerable than the no-feedback condition because $P_{\infty }\left(1\right)$ of the no-feedback case is much smaller than the feedback case.

Figure 11

(a) The maximum value of coupling strength $q_{\max }$ as a function of $\overline{k}$ for the feedback and no-feedback conditions when $m=3$. We can see that $q_{\max }$ of the no-feedback case is larger than that of the feedback case, which indicates that the no-feedback case is more robust compared to the feedback case. (b) The maximum value of coupling strength $q_{\max }$ as a function of $m$ with the feedback condition for different values of $\overline{k}$, showing that increasing $\overline{k}$ or decreasing $m$ will increase $q_{\max }$, i.e., increase the robustness of NetONet.

Figure 12

The giant component for a RR NetONet formed of RR networks with feedback condition $P_{\infty }$ as a function of $p$ for a RR of degree $k=6$ and $m=3$, for two different values of $q$. The curves are obtained using Eq. (51), which shows a first order phase transition when $q$ is large but a second order phase transition when $q$ is small.