Percolation of partially interdependent scale-free networks

Di Zhou, Jianxi Gao, H. Eugene Stanley, Shlomo HavlinPhysical 2013 · DOI · arXiv

Abstract

We study the percolation behavior of two interdependent scale-free (SF) networks under random failure of $1-p$ fraction of nodes. Our results are based on numerical solutions of analytical expressions and simulations. We find that as the coupling strength between the two networks $q$ reduces from 1 (fully coupled) to 0 (no coupling), there exist two critical coupling strengths $q_1$ and $q_2$, which separate three different regions with different behavior of the giant component as a function of $p$. (i) For $q \ge q_1$, an abrupt collapse transition occurs at $p=p_c$. (ii) For $q_2 < q < q_1$, the giant component has a hybrid transition combined of both, abrupt decrease at a certain $p=p_c^{jump}$ followed by a smooth decrease to zero for $p < p_c^{jump}$ as $p$ decreases to zero. (iii) For $q \le q_2$, the giant component has a continuous second-order transition. We find that for $\lambda \le 3$, $q_1 \equiv 1$; and for $\lambda > 3$, $q_1$ decreases with increasing $\lambda$. In the hybrid transition region, the mutual giant component $P_{\infty}$ jumps discontinuously to a very small but nonzero value, and eventually approaches zero at $p_c=0$ for $\lambda < 3$ and at $p_c > 0$ for $\lambda > 3$.

Introduction

Modern infrastructure systems—such as power grids, water supplies, and communication networks—are rarely isolated. They exist as "networks of networks," where the functionality of one node often depends on the status of a node in a different system. While single scale-free (SF) networks are known for their extreme robustness against random failures, previous research has shown that full interdependence makes these systems incredibly fragile. A small failure in one network can trigger a catastrophic cascading collapse across the entire system.

However, real-world systems are rarely fully interdependent. This paper investigates the more realistic scenario of "partial" interdependence, where only a fraction $q$ of nodes in one network depend on nodes in another. By exploring the parameter space of coupling strength $q$ and the network's internal structure (defined by the power-law exponent $\lambda$), this study identifies a novel "hybrid" phase transition that bridges the gap between total collapse and gradual degradation.

Methodology

The research utilizes a combination of analytical mathematical modeling and large-scale simulations:

  1. Generating Functions: The authors use the mathematical framework of generating functions to describe the degree distributions ($P(k) \propto k^{-\lambda}$) and branching processes within the scale-free networks.
  2. Iterative Cascading Framework: They adapt the Parshani et al. model to track the step-by-step failure process. When a node in Network A fails, its dependent counterpart in Network B also fails, potentially causing further fragmentation in B, which then reflects back to A.
  3. Numerical Analysis: Because the generating functions for SF networks lack simple closed-form solutions, the authors solve transcendental equations numerically to determine the size of the "giant component" ($P_{\infty}$)—the functional core of the network.
  4. Monte Carlo Simulations: To validate the theory, simulations were performed on synthetic networks containing up to $1.28 \times 10^6$ nodes.

The Three Regimes of Network Collapse

The study identifies two critical coupling thresholds, $q_1$ and $q_2$, which divide the network's behavior into three distinct regimes based on the strength of interdependence:

1. High Coupling ($q \ge q_1$): Abrupt Collapse

In this regime, the networks are highly interdependent. They function relatively normally as nodes are removed until a critical threshold $p_c$ is reached. At this point, the system undergoes a first-order transition: the giant component vanishes instantly in a total catastrophic collapse.

2. Intermediate Coupling ($q_2 < q < q_1$): The Hybrid Transition

This is the most striking discovery of the paper. In this regime, the network experiences a "hybrid" transition. As $p$ decreases, the giant component suffers a sudden, discontinuous "jump" in size (an abrupt drop), but it does not vanish entirely. Instead, a tiny, resilient functional core remains. This core then degrades smoothly (a continuous transition) as more nodes are removed, eventually hitting zero.

3. Low Coupling ($q \le q_2$): Continuous Decay

When interdependence is low, the networks behave more like isolated systems. There is no sudden collapse; instead, the giant component shrinks gradually and predictably as nodes fail, following a standard second-order transition.

The Role of Network Topology ($\lambda$)

The power-law exponent $\lambda$ of the degree distribution significantly influences these transitions.

  • Fat-Tailed Networks ($\lambda \le 3$): For these networks (common in the real world, such as the Internet), the authors find that $q_1$ is always 1. This means that unless the networks are fully coupled, they will not experience a total first-order collapse. Furthermore, in the hybrid and continuous regimes, the final collapse point $p_c$ remains at zero, meaning the network is theoretically "un-killable" by random failure until every single node is removed.
  • Thin-Tailed Networks ($\lambda > 3$): For these networks, $q_1$ decreases as $\lambda$ increases. These systems are more prone to hybrid transitions even at lower levels of coupling and have a non-zero $p_c$, making them inherently more fragile than their $\lambda \le 3$ counterparts.

Key Findings and Diagnostics

A critical diagnostic tool identified in the study is the Number of Iterations (NOI) required for a failure cascade to stabilize. The authors found that the NOI peaks sharply at the transition point $p_c^{jump}$. In the hybrid regime, this peak occurs exactly when the giant component takes its discontinuous dive to a smaller value, providing a clear signature of the impending structural shift.

Numerical results showed that in the hybrid regime, the giant component might jump from a significant fraction of the network down to a remnant as small as $10^{-2}$ or $10^{-4}$ before finally fading away. This highlights the existence of a "resilient core" that persists even after the majority of the system has failed.

Conclusion

This research provides a theoretical map for understanding the stability of interconnected systems. By identifying the hybrid transition, the authors show that partial interdependence allows for a middle ground between total robustness and total fragility. For real-world infrastructure, this suggests that reducing coupling strength below $q_1$ can prevent total catastrophic failure, even if it cannot prevent a significant partial collapse. Future work remains to be done on targeted attacks and more complex many-to-many dependency mappings.

Summary updated

Abstract

We study the percolation behavior of two interdependent scale-free (SF) networks under random failure of 1-p fraction of nodes. Our results are based on numerical solutions of analytical expressions and simulations. We find that as the coupling strength between the two networks q reduces from 1 (fully coupled) to 0 (no coupling), there exist two critical coupling strengths q(1) and q(2), which separate three different regions with different behavior of the giant component as a function of p. (i) For q≥q(1), an abrupt collapse transition occurs at p=p(c). (ii) For q(2)<q<q(1), the giant component has a hybrid transition combined of both, abrupt decrease at a certain p=p(c)(jump) followed by a smooth decrease to zero for p<p(c)(jump) as p decreases to zero. (iii) For q≤q(2), the giant component has a continuous second-order transition (at p=p(c)). We find that (a) for λ≤3, q(1)≡1; and for λ>3, q(1) decreases with increasing λ. Here, λ is the scaling exponent of the degree distribution, P(k)[proportionality]k(-λ). (b) In the hybrid transition, at the q(2)<q<q(1) region, the mutual giant component P(∞) jumps discontinuously at p=p(c)(jump) to a very small but nonzero value, and when reducing p, P(∞) continuously approaches to 0 at p(c)=0 for λ<3 and at p(c)>0 for λ>3. Thus, the known theoretical p(c)=0 for a single network with λ≤3 is expected to be valid also for strictly partial interdependent networks.
BibTeX
@inproceedings{zhou2013percolation,
  author = {Di Zhou and Jianxi Gao and H. Eugene Stanley and Shlomo Havlin},
  title = {{Percolation of partially interdependent scale-free networks}},
  booktitle = {Physical},
  year = {2013},
  doi = {10.1103/physreve.87.052812},
}
Figure