PaperlayerView exact revision on arXiv

Source-linked AI summary

Suppressing cascades of load in interdependent networks

Charles D. Brummitt, Raissa M. D'Souza, E. A. Leicht

arXiv:1106.4499v2physics.soc-ph

TL;DR

The paper examines how interdependence shapes cascading load in modular and real power-grid networks. Using multitype branching processes and simulations, it identifies benefits and dangers of connectivity, including tradeoffs for infrastructure management.

  • Problem

    Interdependence increasingly affects cascading behavior across power grids and other critical infrastructure, requiring better understanding of its risks and benefits.

  • Method

    The authors combine multitype-network mathematics with sandpile models to derive branching-process approximations and analyze cascades on synthetic and real interacting networks.

  • Results

    Some interdependence suppresses largest local avalanches, whereas excessive connectivity enables inflicted load and increases capacity, fueling larger global cascades.

  • Takeaways & Limitations

    Infrastructure owners may prefer an intermediate level of interconnection, although individually beneficial connections can amplify cascades across the entire system.

  • Takeaways & Limitations

    More realistic optimal-connectivity estimates require models combining these results with electrical, economic, physical, and connection-building costs.

Abstract

from arXiv · show

Understanding how interdependence among systems affects cascading behaviors is increasingly important across many fields of science and engineering.Inspired by cascades of load shedding in coupled electric grids and other infrastructure, we study the Bak-Tang-Wiesenfeld sandpile model on modular random graphs and on graphs based on actual, interdependent power grids. Starting from two isolated networks, adding some connectivity between them is beneficial, for it suppresses the largest cascades in each system. Too much interconnectivity, however, becomes detrimental for two reasons. First, interconnections open pathways for neighboring networks to inflict large cascades. Second, as in real infrastructure, new interconnections increase capacity and total possible load, which fuels even larger cascades. Using a multitype branching process and simulations we show these effects and estimate the optimal level of interconnectivity that balances their tradeoffs. Such equilibria could allow, for example, power grid owners to minimize the largest cascades in their grid. We also show that asymmetric capacity among interdependent networks affects the optimal connectivity that each prefers and may lead to an arms race for greater capacity. Our multitype branching process framework provides building blocks for better prediction of cascading processes on modular random graphs and on multi-type networks in general.

A. Locally stabilizing effect of interconnections

Interconnections can suppress an individual network’s largest cascades, but only up to an optimal critical connectivity, beyond which inflicted load and added capacity increase cascade risk.

  • A. Locally stabilizing effect of interconnections: Increasing interconnectivity p suppresses an individual network’s largest cascades, but only up to a critical point p∗.This effect was reported for coupled random regular graphs and is associated with a stable minimum in large-cascade probability.
  • A. Locally stabilizing effect of interconnections: 80% and 70% are the drops in Pr(Taa > 1000) and Pr(Ta > 1000), respectively, from p = 0.001 to p∗≈0.075 ± 0.01.The first metric concerns local cascades beginning in network a; the second does not distinguish where the cascade begins.
  • A. Locally stabilizing effect of interconnections: Large local cascades decrease for small p and increase for large p, while large inflicted cascades become more frequent as p increases.The average of these effects has a stable minimum at p∗≈0.075 ± 0.01 in R(3)-B(p)-R(3) simulations.
  • A. Locally stabilizing effect of interconnections: The qualitative stabilization curve persists when system size, internal degree, or narrow degree-distribution type changes, although p∗ may shift slightly.Adding edges within a single isolated network does not produce the same minimum.
  • A. Locally stabilizing effect of interconnections: Adding connections diverts load toward neighboring networks, where it tends to be absorbed rather than amplified and returned.The branching-process first moments show same-network topplings decreasing and neighboring-network topplings increasing with p.
  • A. Locally stabilizing effect of interconnections: Too many interconnections let diverted load return more easily and augment network capacity and average load, increasing large avalanches.The model uses node degree as capacity, so added external edges increase both capacity and available load.

B. Globally destabilizing effect of interconnections

Interconnections can enlarge global cascades because added edges extend the total-avalanche tail, with increased capacity contributing more strongly than interdependence alone.

  • B. Globally destabilizing effect of interconnections: Increasing p extends the right-hand tail of the total avalanche-size distribution s(t) when the two networks are treated as one system.The largest avalanches increase with interconnectivity in simulations of coupled random 3-regular graphs.
  • B. Globally destabilizing effect of interconnections: Increased total capacity, and hence average load available for cascades, amplifies global avalanches more significantly than increased interdependence.In the model, new edges raise node degrees and capacities; rewiring experiments did not significantly enlarge the largest avalanches.
  • B. Globally destabilizing effect of interconnections: Additional edges enlarge the largest global cascades by an amount on the order of the added number of interconnections.This comparison is shown using rank-size plots of the largest avalanches.
  • B. Globally destabilizing effect of interconnections: The amplification is relevant to infrastructure because additional capacity and demand often accompany or motivate new interconnections.The paper contrasts adding new external connections with rewiring existing internal edges.

C. Interconnectivity that mitigates cascades of different sizes

The interconnectivity that best suppresses cascades depends on cascade size: isolation helps with the smallest cascades, while large-cascade mitigation favors an intermediate stable coupling.

  • Small-cascade probability increases monotonically with interconnectivity, so networks mitigating the smallest cascades seek isolation, p = 0.
  • Intermediate-cascade mitigation can favor isolation or strong coupling, depending on whether initial interconnectivity lies below or above the unstable critical point p∗≈0.05.
  • Networks mitigating large cascades seek the stable equilibrium p∗≈0.075 ± 0.01 rather than either complete isolation or maximal coupling.
  • Interconnections that suppress large local cascades can amplify larger cascades in the whole system, while isolation amplifies a network’s large cascades.

D. Capacity disparity

Capacity disparity makes interdependence more damaging for the lower-capacity network and gives the two networks different preferred interconnectivity levels.

  • Lower-capacity networks suffer comparatively larger inflicted cascades but still prefer some interconnectivity, at a lower level than higher-capacity networks.
  • When z_b > z_a, cascades inflicted from b to a are larger on average than cascades inflicted from a to b.
  • For power grids, asymmetric capacity can create an arms race in which each owner seeks greater capacity to withstand cascades inflicted by neighboring networks.

E. Incentives and equilibria in power grids

In power-grid simulations, interconnectivity and load disparity jointly determine whether inflicted or local cascades dominate, producing frustrated rather than mutually attainable equilibria.

  • The power-grid analysis uses three natural connectivity levels: zero, the original eight interconnections, or eight added interconnections matching the empirical degree distribution.
  • Figure 7 compares the largest inflicted and local avalanches in grid d across interconnection counts and load disparities using log-log rank-size plots.
  • For 16 interconnections, inflicted cascades in d become as large as local cascades at the critical load disparity r∗≈15; with 8 interconnections, r∗> 20.
  • Increasing interconnections or increasing r amplifies the largest inflicted cascades in d, and inflicted cascades dominate local cascades above r∗≈15.
  • The observed load disparity is r≈0.7, so grid d prefers more interconnections and grid c fewer than under equal loading, leaving only a frustrated or semi-stable equilibrium.

III. DISCUSSION

The discussion frames interdependence as a tradeoff: moderate coupling can reduce local large avalanches, but excessive coupling increases inflicted load and system capacity, while the mathematical framework extends to multitype networks.

  • III. DISCUSSION: For similar-capacity coupled networks, benefits from diverting load and detriments from inflicted load and added capacity balance at a stable critical interconnectivity.
  • III. DISCUSSION: Tuning interconnectivity to suppress one cascade-size range amplifies cascades in other ranges, including larger local or global avalanches.
  • III. DISCUSSION: Individual grids may benefit from some connections, whereas those connections can amplify global cascades; realistic optimization would also include economic and physical grid considerations.
  • III. DISCUSSION: The analysis focuses on two interacting networks and stable underlying topologies, while topological connectivity failures and other dynamics require additional models.
  • III. DISCUSSION: The branching-process framework derives sandpile cascade approximations from degree distributions for multitype networks and can extend from two types to finitely many types.
  • III. DISCUSSION: The method tracks toppling events by network and derives their branch distributions, enabling multitype generating-function calculations of cascade sizes.

D. Solving for the coefficients asymptotically (and why standard techniques fail)

The paper seeks generating-function singularities to approximate large-cascade coefficients, but standard finite-singularity methods fail for the coupled networks studied. The resulting entire generating functions leave asymptotic coefficient analysis unresolved.

  • D. Solving for the coefficients asymptotically (and why standard techniques fail): The analysis seeks asymptotic behavior of s_a(t_a,t_b) and s_b(t_a,t_b) by solving for inverse generating functions and expanding them.The inverse functions are intended to support coefficient asymptotics as cascade sizes grow.
  • D. Solving for the coefficients asymptotically (and why standard techniques fail): The only solution of the derivative equations does not reproduce the correct isolated-network singularities and must be discarded.Although the equations vanish there, the derivatives required by the singularity construction do not.
  • D. Solving for the coefficients asymptotically (and why standard techniques fail): For Bernoulli-coupled random regular graphs and power grids c,d, the generating functions have no finite singularities in the relevant complex domain.The finite-singularity condition can vanish only in boundary or divergent cases described in the analysis.
  • D. Solving for the coefficients asymptotically (and why standard techniques fail): Standard isolated-network asymptotic expansions therefore cannot be applied to the coupled generating functions.The paper notes that the functions are entire and their singularities occur only at infinity.
  • D. Solving for the coefficients asymptotically (and why standard techniques fail): Hayman’s method could handle entire generating functions, but it requires closed-form generating functions unavailable for the synthetic and real interacting networks.Developing methods for multidimensional generating functions with singularities at infinity remains an open challenge.

V. APPENDIX: EFFECTIVE DEGREE DISTRIBUTIONS IN MULTITYPE NETWORKS

The configuration model changes the effective inter-degree distribution because valid multitype graphs require matching inter-network edge stubs. The correction is governed by conditional convolution probabilities and can be negligible when the degree distributions overlap substantially.

  • V. APPENDIX: EFFECTIVE DEGREE DISTRIBUTIONS IN MULTITYPE NETWORKS: Configuration-model generation must match inter-network edge stubs, requiring the total stubs from network a to b to equal those from b to a.This constraint applies when constructing interacting multitype networks.
  • V. APPENDIX: EFFECTIVE DEGREE DISTRIBUTIONS IN MULTITYPE NETWORKS: The effective inter-degree distribution is conditional on equal total inter-stubs, rather than simply the input distribution.The conditioning arises because independently drawn degree sequences are retained only when their totals match.
  • V. APPENDIX: EFFECTIVE DEGREE DISTRIBUTIONS IN MULTITYPE NETWORKS: The correction factor is formed from convolutions of the two networks’ inter-degree distributions.The relevant convolution is evaluated at the proposed total inter-degree and normalized over valid totals.
  • V. APPENDIX: EFFECTIVE DEGREE DISTRIBUTIONS IN MULTITYPE NETWORKS: For systems of roughly 10^4 nodes, repeatedly generating degree sequences until they are valid is feasible, taking merely seconds.For millions of nodes, redrawing node degrees can improve generation efficiency but does not remove the conditioning effect.
  • V. APPENDIX: EFFECTIVE DEGREE DISTRIBUTIONS IN MULTITYPE NETWORKS: When the convolution supports overlap substantially, the effective inter-degree distribution is approximately the input distribution and the correction can be neglected.The Bernoulli and Correlated-Bernoulli distributions used in the study have identical expected total inter-degree.

S1.1. How p∗depends on system size, connectivity, type of degree distribution

The minimum interconnectivity p* is positive and appears qualitatively robust across system sizes and degree-distribution choices. Its value nevertheless shifts with dissipation, cutoff, and internal degree, while cascade-size ranges can favor different connectivities.

  • S1.1. How p* depends on system size, connectivity, type of degree distribution: The central result is a positive minimum p* in the chance of a large cascade when a fraction p of nodes connects to another network.The qualitative form of Pr(T_a > C) appears generic in the studied systems.
  • S1.1. How p* depends on system size, connectivity, type of degree distribution: Doubling system size while keeping cutoff C and dissipation f fixed does not significantly change the large-cascade curve because dissipation limits large cascades.Doubling both system size and cutoff while halving dissipation slightly decreases p*.
  • S1.1. How p* depends on system size, connectivity, type of degree distribution: p*≈0.12 ± 0.02 remains qualitatively similar for a half-sized system with C=500 and f=0.02, and is stable across 200≤C≤800.These results come from simulations with 1000 nodes per network.
  • S1.1. How p* depends on system size, connectivity, type of degree distribution: p*≈0.2 for coupled random 4-regular graphs, compared with p*≈0.12 for equally sized random 3-regular graphs.Higher internal degree increases capacity and produces a wider range of optimal p.
  • S1.1. How p* depends on system size, connectivity, type of degree distribution: Introducing modest degree heterogeneity with Erdős-Rényi graphs yields results similar to those for random regular graphs.Heavy-tailed degree distributions were not tested because they rarely occur in the infrastructure networks motivating the study.
  • S1.1. How p* depends on system size, connectivity, type of degree distribution: Different cascade-size ranges favor different interconnectivities, while large cascades on R(3)-B(p)-R(3) have a stable minimum near p*≈0.075.Intermediate cascade probabilities change concavity near cascade size 350, whereas large cascades have a stable critical point near 0.075.

S1.3. Increasing capacity fuels larger system-wide cascades

The appendix separates the effects of link direction and added capacity on global cascades in synthetic and real coupled grids. Simulations indicate that increased capacity, rather than link direction, largely explains the observed amplification.

  • S1.3. Increasing capacity fuels larger system-wide cascades: Correlated-Bernoulli coupling changes internal stubs into external stubs, allowing the study to separate link direction from added capacity.The model uses node degree as capacity, so extra edges also increase load-holding capacity.
  • S1.3. Increasing capacity fuels larger system-wide cascades: Global avalanche sizes change little under correlated coupling, indicating that link direction alone does not significantly amplify global cascades.The comparison uses coupling that preserves the relevant total degree while redirecting stubs.
  • S1.3. Increasing capacity fuels larger system-wide cascades: Eight additional interconnections between power grids c and d produce larger global cascades by an amount on the order of the added capacity.This supports capacity, rather than link direction, as the main explanation for system-wide amplification.
  • S1.3. Increasing capacity fuels larger system-wide cascades: For 16 interconnections, the critical load disparity is approximately 15, where the largest inflicted cascade from c to d matches the largest local cascade in d.Increasing d’s interconnections or the load disparity makes inflicted cascades larger; deleting interconnections reverses that comparison.
  • S1.3. Increasing capacity fuels larger system-wide cascades: For 16 interconnections, simulations bound the critical disparity as 10⪅r*⪅20; with 8 interconnections, r* is evidently greater than 20.At r=10 inflicted cascades are smaller, while at r=20 they are larger; with 8 links they remain smaller at r=20.

S3.1. Comparing theory and experiment

The branching-process theory generally agrees with simulations, while interconnections alter cascade distributions and increasingly correlate avalanche sizes across networks.

  • Comparing theory and experiment: Halving dissipation to f = 0.05 noticeably extends avalanche-distribution tails, making the largest avalanches larger.The simulations use independent power-grid networks and compare them with branching-process predictions.
  • Comparing theory and experiment: Network structure affects inflicted avalanche distributions: an outlier node with one external and ten internal links produces a high probability of cascades of size 8, 9, or 10.The outlier’s high internal degree explains why cascades leaking from network d into c topple these numbers of c-nodes.
  • Comparing theory and experiment: Increasing Bernoulli coupling p makes cascade sizes increasingly correlated and moves the joint distribution farther from the product of its marginals.This indicates that one-dimensional marginal comparisons become insufficient as coupling increases.
  • Comparing theory and experiment: Theory and simulation are compared using joint avalanche probabilities, including Pr(Ta = 10, Tb = x) across coupling values p = 0.005, 0.01, 0.1.The theoretical joint probabilities are computed with multidimensional Lagrange inversion.

S3.4. Capacity disparity

Capacity asymmetry makes cascades inflicted from larger-capacity networks larger than those traveling in the opposite direction, although the heuristic prediction is only qualitative.

  • Capacity disparity: Cascades inflicted from larger-capacity networks to smaller-capacity networks are larger than those in the reverse direction.The paper derives this effect heuristically with a multitype branching process and compares it with simulations.
  • Capacity disparity: The heuristic ratio ⟨sa⟩b/⟨sb⟩a = (1 + za)/(1 + zb) compares the divergent rates of mean inflicted cascade sizes.The individual first moments are infinite in isolation, so their divergence rates are compared instead.
  • Capacity disparity: For unequal regular degrees, simulations consistently produce larger inflicted cascades from the network with greater capacity.The reported ordering is za < zb ⇒ ⟨sa⟩b < ⟨sb⟩a.
  • Capacity disparity: In the R(3)-B(0.005)-R(3) example, the observed ratio is 0.65 ± 0.019 versus the theoretical prediction 4/5, a 20% error.The measured means are ⟨sa⟩b = 0.086 ± 0.019 and ⟨sb⟩a = 1.32 ± 0.023.

S3.5. Computational challenges in showing the locally stabilizing effect

Computing joint avalanche distributions can demonstrate local stabilization, but truncation omits tail probability and larger coefficients require substantial computation.

  • Computational challenges: Multidimensional Lagrange inversion computes avalanche probabilities sa(ta, tb) for 0 ≤ ta, tb ≤ 10 to study locally stabilizing interconnections.The resulting marginalized distributions are compared across interconnectivity values.
  • Computational challenges: Truncating each network’s avalanche size at 10 removes right-tail probability because avalanches with ta = 10 and tb = 11, 12, or 13 remain possible.Thus the plotted tail does not represent the full marginalized distribution.
  • Computational challenges: Computing sa(ta, tb) for 0 ≤ ta, tb ≤ 20 on a typical laptop would take about a week.The Cauchy-integral approach still requires iterating the self-consistency equations at least ta + tb + 1 times and integrating increasingly large expressions.
  • Computational challenges: Increasing interconnectivity p smears cascades across networks and makes avalanches large in both networks more frequent.This pattern appears in the computed joint distribution for p = 0, 0.1, 1.
Loading 1106.4499v2…