PaperlayerView exact revision on arXiv

Source-linked AI summary

Catastrophic cascade of failures in interdependent networks

Sergey V. Buldyrev, Roni Parshani, Gerald Paul, H. Eugene Stanley, Shlomo Havlin

arXiv:0907.1182v1cond-mat.dis-nn

TL;DR

Modern systems depend on multiple networks whose failures can cascade, but network robustness has often been studied primarily for isolated networks. The paper introduces a general interdependent-network model and solves its cascading failures analytically using percolation theory and generating functions. For two interdependent ER networks, the critical average degree is p_c = 2.4554/a, with numerical simulations in excellent agreement with theory.

  • Problem

    Modern systems depend on multiple networks whose failures can cascade, but network robustness has often been studied primarily for isolated networks.

    Source: §I · p. 1

  • Method

    The paper introduces a general interdependent-network model and solves its cascading failures analytically using percolation theory and generating functions.

    Source: §I · p. 1

  • Results

    For two interdependent ER networks, the critical average degree is p_c = 2.4554/a, with numerical simulations in excellent agreement with theory.

    Source: §IV · p. 4

  • Takeaways & Limitations

    Broader degree distributions make interdependent networks more vulnerable to random failure, so robust-network design must account for interdependence.

    Source: §I · p. 1, §VI · p. 4

Abstract

from arXiv · show

Many systems, ranging from engineering to medical to societal, can only be properly characterized by multiple interdependent networks whose normal functioning depends on one another. Failure of a fraction of nodes in one network may lead to a failure in another network. This in turn may cause further malfunction of additional nodes in the first network and so on. Such a cascade of failures, triggered by a failure of a small faction of nodes in only one network, may lead to the complete fragmentation of all networks. We introduce a model and an analytical framework for studying interdependent networks. We obtain interesting and surprising results that should significantly effect the design of robust real-world networks. For two interdependent Erdos-Renyi (ER) networks, we find that the critical average degree below which both networks collapse is <k_c>=2.445, compared to <k_c>=1 for a single ER network. Furthermore, while for a single network a broader degree distribution of the network nodes results in higher robustness to random failure, for interdependent networks, the broader the distribution is, the more vulnerable the networks become to random failure.

I. INTRODUCTION

Modern systems increasingly consist of interdependent networks whose failures can cascade across networks. The paper introduces an analytical framework showing that interdependence changes robustness expectations established for isolated networks.

I. INTRODUCTION

  • Interdependent networks can recursively transmit failures, so a small initial node failure may fragment all networks.Power and communication networks exemplify mutual dependence: communication nodes need power, while power stations need network control.Source: §I · p. 1
  • The paper presents a general model and exact analytical solutions for the critical node-removal fraction causing complete network fragmentation.The framework uses percolation theory and generating functions.Source: §I · p. 1
  • Broader degree distributions increase vulnerability to random failure in interdependent networks, reversing the robustness trend observed for single networks.The paper argues that robust-network design methods must account for interdependence.Source: §I · p. 1

II. THE MODEL

The model represents mutually dependent networks whose functional core is the mutually connected giant component. A recursive failure cascade tracks alternating fragmentation across the networks until no further removals occur.

II. THE MODEL

  • Each network’s functionality requires a spanning cluster, because nodes outside it become nonfunctional and can disable dependent nodes in other networks.This identifies the mutually connected giant component as the system’s functional core.Source: §II · p. 2
  • The model assumes two equal-sized networks with independent degree distributions and one-to-one node dependence, followed by an initial removal leaving fraction p functional.Corresponding dependent nodes and their edges are removed simultaneously.Source: §II · p. 2
  • A mutually connected cluster contains corresponding nodes that belong to connected clusters in both networks, with disconnected clusters removed as nonfunctional.The model focuses on the mutually connected giant component because it is the only functional system part.Source: §II · p. 2
  • The analysis asks for the critical p below which no mutual giant component exists and for its size as a function of p.These quantities are obtained through a physically interpreted recursive cascade of failures.Source: §II · p. 2
  • The cascade alternates between identifying clusters in one network and removing cross-cluster edges in the other until splitting and edge removal stop.The sequence proceeds through alternating a- and b-clusters.Source: §II · p. 2

III. ANALYTICAL SOLUTION

The analytical solution uses generating functions to follow the shrinking sequence of giant components produced by alternating failures. Its limiting equations determine the mutual giant component and the critical transition where a nonzero solution first appears.

III. ANALYTICAL SOLUTION

  • Generating functions are introduced to solve the cascade analytically for the degree distributions and branching processes.Random node removal changes the remaining degree distribution before successive giant-component calculations.Source: §III · p. 2
  • The cascade generates a nested sequence of alternating giant components whose node fractions decrease recursively across stages.The mutual giant-component fraction is the limiting value of this sequence as the stage index tends to infinity.Source: §III · p. 3
  • The mutual giant component is obtained from the limiting fixed-point equations, while the trivial zero solution represents complete loss of the giant component.A nonzero solution exists only when p is sufficiently large.Source: §III · p. 3
  • The critical point occurs when the line y = x touches the nonlinear solution curve, yielding equations for both critical p and critical mutual-component size.This tangency marks emergence of the nontrivial solution.Source: §III · p. 3

IV. ER NETWORKS

For interdependent ER networks, the model yields explicit critical thresholds through generating-function equations, with numerical simulations agreeing with the theory.

IV. ER NETWORKS

  • For ER networks, Poisson degree distributions reduce the interdependent-network equations to an explicitly solvable system.Source: §IV · pp. 3–4
  • The critical case is obtained from a tangential intersection condition after reducing the system to a single equation.The critical value of p is then determined from Eq. (19).Source: §IV · p. 4
  • For unequal average degrees a and b, pc and P∞ vary with the ratio a/b; equal degrees permit the closed-form solution above.Source: §IV · p. 4
  • fc = 0.28467, pc = 2.4554/a, and P∞ = 1.2564/a for equal-degree ER networks.Numerical simulations are in excellent agreement with the analytical results.Source: §IV · p. 4

V. SCALE-FREE NETWORKS

For scale-free interdependent networks, mutual percolation retains a finite threshold even where ordinary percolation would have a vanishing threshold.

V. SCALE-FREE NETWORKS

  • pc remains finite for scale-free interdependent networks with λA > 2, unlike regular percolation where pc → 0 for λA ≤ 3.Source: §V · p. 4
  • For λA ≤ 3, the generating function has a singularity that produces a nontrivial giant-component solution.The solution is z = 1 − (pκA)^(1/(3−λA)).Source: §V · p. 4
  • The single-network giant-component fraction scales as PA(p) = (pκA)^(1/(3−λA))⟨kA⟩ for λA > 2.Source: §V · p. 4
  • µ = 1/[(3−λA)(3−λB)] > 1, so sufficiently small p lacks a mutual giant component and the system undergoes a transition at pc > 0.Source: §V · p. 4

VI. ROBUSTNESS OF INTERDEPENDENT NETWORKS

Interdependence reverses the robustness advantage of broad degree distributions: broader networks are more vulnerable to random attack than narrower ones.

VI. ROBUSTNESS OF INTERDEPENDENT NETWORKS

  • Broader degree distributions produce higher pc than narrower distributions in interdependent networks.Simulations of scale-free, ER, and random-regular networks with ⟨k⟩ = 4 agree with the analytical results.Source: §VI · p. 4
  • Random interconnections can pair high-degree nodes with low-degree nodes across networks, while failures remove corresponding nodes and edges in the partner network.Source: §VI · p. 4
  • Hubs that support robustness in single networks become vulnerable during cascading failures in interdependent networks.Source: §VI · p. 4
  • At fixed average degree, broader distributions create more low-degree nodes, which are more easily disconnected and undermine robustness.Source: §VI · p. 4

VII. FINITE SIZE EFFECTS

Finite networks smooth the sharp mutual-percolation transition, while cascade convergence becomes increasingly slow near the critical point.

VII. FINITE SIZE EFFECTS

  • The analytical treatment assumes N → ∞, while finite networks retain relative fluctuations that decrease with system size.Source: §VII · p. 4
  • As N → ∞, P∞(p) becomes a step function: 0 for p < pc and 1 for p > pc.Finite networks instead have a range of p values where a mutual giant component exists with probability P∞(p).Source: §VII · p. 4
  • The finite-size transition width scales as 1/√N because fluctuations in the remaining-node fraction determine whether pa exceeds pc.Source: §VII · pp. 4–5
  • For p > pc, the average number of cascade stages diverges proportionally to ln N/√(p − pc).Source: §VII · p. 5
  • Near pc, the iterative process has roots separated by √(p − pc), causing convergence to slow as the threshold is approached.Source: §VII · p. 5
Loading 0907.1182v1…