Robustness of a network formed of spatially embedded networks

We present analytic and numeric results for percolation in a network formed of interdependent spatially embedded networks. We show results for a treelike and a random regular network of networks each with (i) unconstrained dependency links and (ii) dependency links restricted to a maximum Euclidean length $r$. Analytic results are given for each network of networks with spatially unconstrained dependency links and compared to simulations. For the case of two fully interdependent spatially embedded networks it was found [Li et al., Phys. Rev. Lett. 108, 228702 (2012)] that the system undergoes a first-order phase transition only for $r>r_c\approx 8$. We find here that for treelike networks of networks (composed of $n$ networks) $r_c$ significantly decreases as $n$ increases and rapidly $\left(n\ge 11\right)$ reaches its limiting value of 1. For cases where the dependencies form loops, such as in random regular networks, we show analytically and confirm through simulations that there is a certain fraction of dependent nodes, $q_{\max }$, above which the entire network structure collapses even if a single node is removed. The value of $q_{\max }$ decreases quickly with $m$, the degree of the random regular network of networks. Our results show the extreme sensitivity of coupled spatial networks and emphasize the susceptibility of these networks to sudden collapse. The theory proposed here requires only numerical knowledge about the percolation behavior of a single network and therefore can be used to find the robustness of any network of networks where the profile of percolation of a singe network is known numerically.

Figure 1

(a) Several examples of possible structures of the network of networks. Within the networks we have connectivity links and between the networks we have dependency links. Examples include a line (top left), a tree (top center), a star (top right), a random regular network of networks where each network has $m=2$ dependencies (bottom left), and a random regular network of networks with $m=3$ (bottom right). (b) A graphical representation of $r$, the length of the dependency links.

Figure 2

Illustration of treelike network of networks and looplike network of networks. (a) In this treelike network of networks the mutually interdependent nodes are distinguished by color and the treelike topology guarantees that the size of a mutually interdependent set be exactly $n$ (assuming full interdependency, $q=1$, as in this example). (b) In this network of networks with loops the dependency behavior is identical to (a) because the added dependency links are redundant and do not change the partition to sets of mutually interdependent nodes. Thus, with respect to dependency and cascading failures, (b) can be regarded as a treelike network of networks. (c) In contrast, if the loops are not closed, a situation can emerge in which all of the nodes are dependent upon one another, i.e., the size of the set of mutually interdependent nodes can be up to $N\times n$. Cases (a) and (b) are described in Sec. 2 and case (c) is described in Sec. 3.

Figure 3

Theory for $P_{\infty }\left(x\right)$, the size of the giant component, after a number of iterations is shown as the thick black curve and 40 simulated realizations on lattices of size $N=500\times 500$ are shown as the lighter curves at $p=0.942<p_c=0.944$. (a) $P_{\infty }$ as a function of the number of iterations, $i$, is shown to fit well with the theory of Eq. (1). These results are for five networks in a line, yet for this method the shape of the tree has no effect on the number of iterations. (b) $P_{\infty }$ as a function of $t$ iterations according to the method in Gao et al. [21] for five networks in a line fits well with the theory.

Figure 4

(a) Theory (lines) and simulations (symbols) of the size of the giant component, $P_{\infty }\left(x\right)$, as a function of the fraction of surviving nodes $p$, for networks of interdependent lattices of size $N=250\times 250$ with treelike structure are shown. These results are again for a network of networks in a line yet the results are the same for any other tree formation. Results are shown for $n=2$ (red stars), $n=3$ (blue triangles), $n=5$ (green circles), $n=7$ (purple squares), and $n=10$ (yellow-green x's). As shown, all of the transitions are first order and the simulations fit well with the theory. Further, increasing the number of networks is seen to quickly increase $p_c$, indicating that the system becomes more vulnerable as $n$ increases. (b) Here we observe that the number of iterations (NOI) it takes for the system to arrive at steady-state diverges at the critical threshold $p_c$. The number of iterations at $p_c$ increases both with the number of networks, $n$, and the size of the networks, $N$ [51].

Figure 5

(a) The critical threshold $p_c$ as a function of the number of networks, $n$, in a star formation is plotted for $q=0.5$ (red x's), $q=0.6$ (blue diamonds), $q=0.7$ (green squares), $q=0.8$ (purple circles), and $q=1.0$ (yellow-green stars). A fraction $1-p$ of nodes are removed only from the central network. Simulations on lattices with $N=250\times 250$ $\left(n>2\right)$ or $N=500\times 500$ $\left(n=2\right)$ show excellent agreement with the theory. (b) $P_{\infty }\left(p_c\right)$, the size of the giant component at criticality, is shown as a function of the number of networks (symbols are as before). Simulations on lattices of size $N=500\times 500$ fit well with the theory.

Figure 6

(a) Simulations of $P_{\infty }$, the fractional size of the giant component as a function of the fraction of surviving nodes $p$ for $n$ fully interdependent $\left(q=1\right)$ spatial networks of size $N=100\times 100$ in a tree formation with $r=2$ are shown. As the number of networks increases the transition becomes first-order (here at $n=5$). (b) The percolation threshold $p_c$ is plotted as a function of $r$ (number of lattice units) for lattices with $N=250\times 250$ with symbols as defined in Fig. 6. The change from a second-order to a first-order transition occurs at $r_c$, when $p_c$ reaches a maximum. The inset shows how this critical value, $r_c$, varies with the number of networks $n$. The critical dependency length can reach as low as $r_c=1$ if there is a sufficient number of interdependent networks (here $n=11$). Note that already at $r=30$ the $p_c$ becomes very close to the theory of Eqs. (3) and (4) for $r=\infty$. In this case since a fraction $1-p$ was removed from all networks, we must take $p_c^{1/n}$ in order to get results that agree with Eqs. (3) and (6) and Fig. 5. The lines in this figure are a guide to the eye.

Figure 7

The fraction of nodes in the giant component, $P_{\infty }\left(x\right)$ as a function of $p$ according to both theory (lines) and simulations (symbols) for interdependent lattice networks of size $N=250\times 250$ with random regular dependencies where $r=\infty$ are shown. As seen all of the transitions are first order and the simulations fit well with the theory. We use $n=m+1$ networks in the simulations, but the results depend only on $m$, the number of dependencies, each network has and not on $n$, the total number of networks in the system. Results for (a) different values of $q$ and (b) different values of $m$ are shown.

Figure 8

(a) The critical threshold $p_c$ for an RR network of spatial networks is plotted as a function of $m$, the number of dependencies each network has for several fractions of interdependent nodes $q$. The lines represent the theory according to Eq. (10) and the symbols represent simulations. It is worth noting that once the number of dependencies reaches a certain value, $p_c\to 1$ for a given $q$ value. This $q$ value represents $q_{\max }$, the maximum dependency the system can sustain. (b) The maximum coupling fraction between networks, $q_{\max }$, above which $p_c\to 1$ is plotted as a function of $m$. As seen, $q_{\max }$ decreases rapidly with $m$, indicating that as each network has more dependencies less coupling is required for the network to fail after even the smallest attack. Simulations (symbols) on lattices of size $N=250\times 250$ are shown to fit well with the theory of Eqs. (13) and (14) (lines).

Figure 9

The shift from a second-order to first-order transition at $r_c$ (number of lattice units) occurs where the critical threshold $p_c$ reaches a maximum. This maximum is seen to occur for smaller $r$ as (a) the number of dependent networks increases (with $q=0.4$) and (b) the interdependent fraction, $q$, between the networks increases (with $m=3$). Simulations are performed on lattices of size $N=250\times 250$. The lines are a guide to the eye.