Robustness of a network formed of spatially embedded networks

Louis Shekhtman, Yehiel Berezin, Michael M. Danziger, Shlomo HavlinPhysical 2014 · DOI · arXiv

Infrastructure systems like power grids and communication networks are often physically tied to geographic locations and depend on one another to function. This paper investigates the fragility of these "networks of networks" (NoN), revealing that as more spatial networks are linked, the entire system becomes exponentially more sensitive to failure.

The Fragility of Interdependent Spatial Systems

In real-world scenarios, a power grid might depend on a communication network for control signals, while the communication network requires electricity from the grid. Previous research has shown that such interdependent networks are significantly more fragile than isolated ones. Instead of degrading gradually, these systems often undergo "first-order" phase transitions, meaning they collapse suddenly and completely once a critical threshold of damage is reached.

While earlier models often assumed random connections, real-world infrastructure is spatially embedded, with nodes having specific physical coordinates. A key question addressed here is how the number of networks ($n$) and the topology of their connections affect the system's stability.

Modeling Complex Network Topologies

The researchers explored several "network of networks" configurations, including lines, stars, trees, and random regular networks.

Various topologies of networks of networks, including line, tree, star, and loopy configurations.

To study these systems, the authors combined analytical mathematical derivations with Monte Carlo simulations on large square lattices (up to $4000 \times 4000$ nodes). Their analytical framework is particularly powerful because it only requires the percolation profile of a single isolated network to predict the behavior of the entire coupled system.

Key Insights: The "Power of $n$" and Critical Lengths

The study reveals several critical vulnerabilities:

  • The Impact of $n$: As the number of interdependent networks ($n$) increases, the system's robustness decreases rapidly. The critical threshold $p_c$—the fraction of nodes that must be maintained for the system to survive—increases significantly with $n$.
  • Collapse of Critical Length ($r_c$): For a pair of networks, a sudden collapse typically only occurs if dependency links are long ($r > 8$). However, in a tree configuration of many networks, this critical length $r_c$ drops to 1. This implies that even if networks only depend on their immediate geographic neighbors, the system remains susceptible to catastrophic failure if enough layers are involved.
  • Single-Node Fragility ($q_{max}$): In networks with loops, there exists a maximum coupling fraction $q_{max}$. If the fraction of dependent nodes exceeds this value, the system becomes so unstable that removing just one node can trigger a total collapse.

Results and Implications

The findings highlight the extreme sensitivity of coupled spatial networks. As shown in the researchers' data, the critical threshold $p_c$ rises as more networks are added to the system.

The critical threshold $p_c$ as a function of the number of networks $n$ for different topologies.

For $n=2$, the critical dependency length $r_c$ is approximately 8. However, for $n \ge 11$ in a tree configuration, $r_c$ reaches its limiting value of 1. Furthermore, increasing the number of dependencies per network (the degree $m$ in random regular NoNs) drastically reduces robustness.

These results serve as a warning for infrastructure planning. While interlinking spatial systems can improve efficiency, it also moves the system closer to a tipping point where minor local failures can lead to widespread regional blackouts. Future work may look into heterogeneous networks or 3D spatial embeddings to further refine these models.

Summary updated

Abstract

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) ≈ 8. We find here that for treelike networks of networks (composed of n networks) r(c) significantly decreases as n increases and rapidly (n ≥ 11) 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.
BibTeX
@inproceedings{shekhtman2014robustness,
  author = {Louis Shekhtman and Yehiel Berezin and Michael M. Danziger and Shlomo Havlin},
  title = {{Robustness of a network formed of spatially embedded networks}},
  booktitle = {Physical},
  year = {2014},
  doi = {10.1103/physreve.90.012809},
}
Figure