Robustness of spatial networks and networks of networks

Louis Shekhtman, Michael M. Danziger, Dana Vaknin, Shlomo HavlinComptes 2018 · DOI · arXiv

Abstract

This paper introduces a mathematical framework to model the robustness of hierarchical networks, such as power grids organized from neighborhoods into cities and states. Unlike "flat" networks that collapse all at once, hierarchical systems undergo multiple abrupt failure transitions (jumps) as different levels of the hierarchy disconnect under targeted attack. We present an analytical solution for the size of the giant component and extend the theory to interdependent Networks of Networks (NON).

Introduction: The Vulnerability of Hierarchy

Most studies on network robustness treat systems as either a single "flat" graph or a simple collection of modules. However, real-world infrastructure is almost always hierarchical: nodes are tightly clustered into neighborhoods, which form cities, and then states.

Visualization of a hierarchical network with clustered modules at multiple levels.

Nodes providing "interconnections" between high-level modules (like long-distance power lines) are often the most vulnerable to failure or targeted attack due to their high betweenness and physical exposure. This research models how a network disintegrates when these high-level connectors are systematically removed.

Methodology: Modeling Multi-Layered Systems

The authors employ a Stochastic Block Model (SBM) with overlapping blocks to represent the hierarchy. The structure is defined by two vectors: $\vec{m}$ (the number of modules at each level) and $\vec{k}$ (the average degree of connections at each level).

A targeted attack strategy is simulated, prioritizing nodes with links at the highest hierarchical levels. Using the inclusion-exclusion principle, the authors derived analytical solutions for "cutoff" probabilities ($p_{co}$) for each level, predicting exactly when specific layers of the hierarchy will fragment. This theory was validated using synthetic network simulations with $N = 10^6$ nodes, averaged over multiple runs to ensure statistical significance.

Results: The "Staircase" of Failure

The most striking finding is that hierarchical networks exhibit multiple discontinuities in their giant component ($S$). As nodes are removed (decreasing the occupancy probability $p$), the network doesn't just shrink continuously; it "snaps" at specific thresholds, corresponding to the separation of states, then cities, then neighborhoods.

The giant component size S as a function of node occupancy p, showing multiple abrupt staircase transitions.

The authors derived a specific inequality (Equation 8) that predicts whether a jump will occur. If the density of links at a lower level is high enough compared to the level being attacked, the network will experience an abrupt transition. Furthermore, in "Network of Networks" (NON) scenarios, interdependence increases fragility, often turning continuous transitions into catastrophic first-order collapses. There is near-perfect agreement between the analytical equations and the large-scale simulations.

Conclusion and Future Directions

The predictability of hierarchical collapse through analytical theory provides a foundational tool for assessing infrastructure resilience. While the current model assumes uniform branching ratios and localized dependencies, it highlights the extreme vulnerability of high-level connectors. Future work should address real-world heterogeneity and dynamic loading effects, such as cascading power blackouts where load is redistributed after failures.

Summary updated

Abstract

Many complex networks have recently been recognized to involve significant interdependence between different systems. Motivation comes primarily from infrastructures like power grids and communications networks, but also includes areas such as the human brain and finance. Interdependence implies that when components in one system fail, they lead to failures in the same system or other systems. This can then lead to additional failures finally resulting in a long cascade that can cripple the entire system. Furthermore, many of these networks, in particular infrastructure networks, are embedded in space and thus have unique spatial properties that significantly decrease their resilience to failures. Here we present a review of novel results on interdependent spatial networks and how cascading processes are affected by spatial embedding. We include various aspects of spatial embedding such as cases where dependencies are spatially restricted and localized attacks on nodes contained in some spatial region of the network. In general, we find that spatial networks are more vulnerable when they are interdependent and that they are more likely to undergo abrupt failure transitions than interdependent non-embedded networks. We also present results on recovery in spatial networks, the nature of cascades due to overload failures in these networks, and some examples of percolation features found in real-world traffic networks. Finally, we conclude with an outlook on future possible research directions in this area.
BibTeX
@inproceedings{shekhtman2018robustness,
  author = {Louis Shekhtman and Michael M. Danziger and Dana Vaknin and Shlomo Havlin},
  title = {{Robustness of spatial networks and networks of networks}},
  booktitle = {Comptes},
  year = {2018},
  doi = {10.1016/j.crhy.2018.09.005},
}
Figure