5D Library › Phase Transitions, Critical Slowing Down and Resilience in Complex Dynamical Systems · 中文
Chapter 5 Cascading Failure: Spare Capacity and Interdependence
One component, a blackout
On 14 August 2003 a large part of the north-eastern United States and the Canadian province of Ontario lost power: more than fifty million people were affected and about 61,800 megawatts of load were interrupted. The final report of the joint US–Canada task force grouped the causes into four categories: inadequate understanding of the system, inadequate situational awareness, inadequate tree trimming and inadequate diagnostic support from the reliability coordinators (U.S.–Canada Power System Outage Task Force 2004). It began with a few transmission lines in Ohio: when one line tripped, its power moved onto others, overloading them until they tripped too, and the load moved again. This process of “failure, transfer of load, further failure” is a cascading failure. Like a fold, it lets a system look normal for a long time and then fail over a wide area very quickly; unlike a fold, it is caused by the connections between many components.
The capacity–load model
Evidence
Motter and Lai 2002. One unit of “flow” is sent between every pair of nodes along shortest paths; the load of a node is the number of shortest paths through it (its betweenness); its capacity is , with the tolerance. After one node is removed the loads are redistributed, overloaded nodes fail, the loads are redistributed again, and so on until no node is overloaded; damage is measured by , the size of the largest connected component after the cascade relative to before. In scale-free networks of about 5,000 nodes, removing a random node hardly ever triggered a cascade, while removing the highest-load node did great damage: at more than 60 % of the nodes were affected, and even at , fell by more than 20 %. In homogeneous networks in which every node has degree 3, no cascades occurred even at . In the topology of the western US power grid, whose degree distribution is close to exponential but whose load distribution is skewed, a load-based attack on a single node reduced the largest component to less than half its size even at . The authors concluded that vulnerability comes from heterogeneity of load (Motter and Lai 2002).
Calculation
A scale-free network of 300 nodes (Barabási–Albert model, each newcomer linking to 2 existing nodes) and a homogeneous network with the same number of nodes and almost the same number of links (600 against 597) in which every node has degree 4. Loads are computed with Brandes’s algorithm. For a range of , we remove either the highest-load node or one of 5 random nodes (averaged) and simulate the cascade. The network sizes are illustrative and far smaller than Motter and Lai’s.
Calculation
# Overload cascades (Motter & Lai 2002). Load L_i = number of shortest paths between other
# pairs that pass through i (Brandes's algorithm); capacity C_i = (1 + alpha) L_i0. Remove one
# node, recompute loads, remove every overloaded node, repeat. G = largest component / N.
# Scale-free (Barabasi-Albert, N = 300, m = 2, 597 links) vs homogeneous (all degrees 4, 600 links).
import random
from collections import deque
rng = random.Random(10)
N = 300
def ba(m=2):
adj = {i: set() for i in range(N)}; targets = []
for i in range(m + 1):
for j in range(i): adj[i].add(j); adj[j].add(i); targets += [i, j]
for v in range(m + 1, N):
chosen = set()
while len(chosen) < m: chosen.add(rng.choice(targets))
for t in chosen: adj[v].add(t); adj[t].add(v); targets += [v, t]
return adj
def regular(k=4):
while True: # configuration model, retry until simple
stubs = [v for v in range(N) for _ in range(k)]; rng.shuffle(stubs)
adj = {i: set() for i in range(N)}; ok = True
for a, b in zip(stubs[::2], stubs[1::2]):
if a == b or b in adj[a]: ok = False; break
adj[a].add(b); adj[b].add(a)
if ok: return adj
def loads(adj, alive):
L = dict.fromkeys(alive, 0.0)
for s in alive: # Brandes (2001), unweighted
pred = {v: [] for v in alive}; sig = dict.fromkeys(alive, 0); sig[s] = 1
dist, order, q = {s: 0}, [], deque([s])
while q:
v = q.popleft(); order.append(v)
for w in adj[v]:
if w not in alive: continue
if w not in dist: dist[w] = dist[v] + 1; q.append(w)
if dist[w] == dist[v] + 1: sig[w] += sig[v]; pred[w].append(v)
delta = dict.fromkeys(alive, 0.0)
for w in reversed(order):
for v in pred[w]: delta[v] += sig[v] / sig[w] * (1 + delta[w])
if w != s: L[w] += delta[w]
return {v: x / 2 for v, x in L.items()} # each unordered pair counted twice
def giant(adj, alive):
seen, best = set(), 0
for s in alive:
if s in seen: continue
seen.add(s); st, n = [s], 0
while st:
v = st.pop(); n += 1
for w in adj[v]:
if w in alive and w not in seen: seen.add(w); st.append(w)
best = max(best, n)
return best
def cascade(adj, L0, alpha, first):
alive, rounds = set(adj) - {first}, 0
while True:
L = loads(adj, alive)
over = {v for v in alive if L[v] > (1 + alpha) * L0[v] + 1e-9}
if not over: return giant(adj, alive) / N, rounds
alive -= over; rounds += 1
if __name__ == "__main__":
sf, h = ba(), regular()
L0, Lh = loads(sf, set(sf)), loads(h, set(h))
top, toph = max(L0, key=L0.get), max(Lh, key=Lh.get)
print(f"scale-free: max degree {max(len(v) for v in sf.values())}, top load {L0[top]:.0f}"
f" (mean {sum(L0.values()) / N:.0f}); homogeneous: top load {Lh[toph]:.0f}")
randoms, res = rng.sample(range(N), 5), {}
print(" alpha G after removing: top-load node (rounds) a random node (mean of 5)"
" homogeneous, top-load")
for alpha in (0.0, 0.1, 0.2, 0.3, 0.5, 0.8, 1.2, 1.4, 2.0):
g1, r1 = cascade(sf, L0, alpha, top); res[alpha] = g1
g2 = sum(cascade(sf, L0, alpha, v)[0] for v in randoms) / 5
print(f" {alpha:3.1f} {g1:5.2f} ({r1}) {g2:5.2f}"
f" {cascade(h, Lh, alpha, toph)[0]:5.2f}")
grid = [i / 10 for i in range(31)] # alpha_c on a 0.1 grid up to 3.0
gs = {a: res[a] if a in res else cascade(sf, L0, a, top)[0] for a in grid}
ac = min(a for a in grid if all(gs[b] >= 0.95 for b in grid if b >= a))
print(f"alpha_c (G >= 0.95 at every alpha from here to 3.0, step 0.1): {ac}"
f" (G = {gs[ac]:.2f}; at {ac - 0.1:.1f}: {gs[round(ac - 0.1, 1)]:.2f})")
# scale-free: max degree 28, top load 7510 (mean 395); homogeneous: top load 720
# alpha G after removing: top-load node (rounds) a random node (mean of 5) homogeneous, top-load
# 0.0 0.02 (1) 0.46 0.02
# 0.1 0.17 (3) 0.99 1.00
# 0.2 0.44 (4) 1.00 1.00
# 0.3 0.63 (3) 1.00 1.00
# 0.5 0.79 (2) 1.00 1.00
# 0.8 0.86 (2) 1.00 1.00
# 1.2 0.90 (3) 1.00 1.00
# 1.4 0.96 (2) 1.00 1.00
# 2.0 0.97 (2) 1.00 1.00
# alpha_c (G >= 0.95 at every alpha from here to 3.0, step 0.1): 1.4 (G = 0.96; at 1.3: 0.91)
Load in the scale-free network is extremely uneven: the highest-load node carries 7,510 shortest paths against a mean of 395 per node; in the homogeneous network the maximum is only 720. At any change overloads some node, and even a random removal brings down to 0.46. With 10 % spare capacity, random removals and targeted removals in the homogeneous network do almost no damage (0.99 and 1.00); but removing the highest-load node of the scale-free network leaves at only 0.17, at 0.79 for and at 0.90 for . Defining the critical spare capacity operationally as “ stays at or above 0.95 from this up to 3.0” and scanning in steps of 0.1, for this network (; 0.91 at ): every node needs about 140 % more capacity than its everyday load to withstand an attack on one key node. This is a result for one network and one attacked node, not a universal constant; another randomly generated network would give a different number.
Beyond how much redundancy there is, where it sits matters too. A uniform margin of 10 % is enough for random faults; the failure of a key node needs a far larger margin, which is almost never used in ordinary times and so is the first to go in a budget that looks only at everyday efficiency. “Draining redundancy”, as discussed in Chapter 4, means in a network pushing down to just what random faults require.
Note
Limits of the model. The model assumes that load follows shortest paths, that failed nodes are removed for good and that nobody intervenes; in real grids power flows follow physical laws, and operators shed load and split the network. The model illustrates the relation between heterogeneous load and redundancy; it does not predict the failure of any real grid. The same logic is often used as an analogy for financial contagion; this book makes no judgment about any financial system and gives no investment advice.
Interdependent networks
Evidence
Buldyrev and colleagues 2010. They took as an example the Italian blackout of 28 September 2003, in which the shutdown of power stations caused nodes of the Internet communication network to fail, which in turn caused more power stations to fail. Their model assumes that two networks A and B have the same number of nodes, each randomly wired internally and uncorrelated with the other; that every node in A depends on exactly one node in B and vice versa (one-to-one and bidirectional); and that a node works only if it belongs to the largest connected component of its own network and the node it depends on also works. After a share of A’s nodes is removed at random, failures pass back and forth between the two networks. For two random networks with the same mean degree , a mutually connected giant component exists only above , and at it jumps abruptly to zero (a first-order transition). For a single network a broader degree distribution makes it more robust to random failure; for interdependent networks the opposite holds (Buldyrev et al. 2010).
Calculation
Two random networks of mean degree 4, each of 4,000 nodes. Theory: after a share of nodes is kept, a single network’s giant component satisfies ; with one-to-one interdependence, with . Simulation: only a share of nodes has a partner (Parshani and colleagues’ “partial dependence”); failures are iterated until nothing changes, and the share of A still working is reported.
Calculation
# Interdependent networks (Buldyrev et al. 2010): two random networks A and B, mean degree 4.
# Assumptions: a fraction 1-p of A fails at random; a node works only if it is in the giant
# component of its own network AND its partner in the other network works. One-to-one
# dependence: P = p (1-f)^2, f = exp(-k p (1-f)^2), jump at p_c = 2.4554/k; a single network:
# S = p (1 - exp(-k S)), continuous at 1/k. Simulation: N = 4,000; a share q of nodes has a
# partner (partial dependence, Parshani et al. 2010).
import math, random
rng = random.Random(12)
K, N = 4.0, 4000
def theory_pair(p):
f = 0.0
for _ in range(3000): f = math.exp(-K * p * (1 - f) ** 2)
return p * (1 - f) ** 2
def theory_single(p):
s = 1.0
for _ in range(3000): s = p * (1 - math.exp(-K * s))
return s
def er():
adj = [[] for _ in range(N)]
for _ in range(int(K * N / 2)):
a, b = rng.randrange(N), rng.randrange(N)
if a != b: adj[a].append(b); adj[b].append(a)
return adj
def giant(adj, alive): # alive flags of the largest component
seen, best = [False] * N, []
for s in range(N):
if not alive[s] or seen[s]: continue
comp, st = [s], [s]; seen[s] = True
while st:
for w in adj[st.pop()]:
if alive[w] and not seen[w]: seen[w] = True; st.append(w); comp.append(w)
if len(comp) > len(best): best = comp
out = [False] * N
for v in best: out[v] = True
return out
def mutual(A, B, partner, p):
aliveA, aliveB = [rng.random() < p for _ in range(N)], [True] * N
while True:
aliveA = giant(A, aliveA)
for v in range(N):
if partner[v] is not None and not aliveA[v]: aliveB[partner[v]] = False
aliveB = giant(B, aliveB); changed = False
for v in range(N):
if partner[v] is not None and aliveA[v] and not aliveB[partner[v]]:
aliveA[v] = False; changed = True
if not changed: return sum(aliveA) / N
if __name__ == "__main__":
print(f"theory: single network p_c = {1 / K:.3f}; coupled pair p_c = {2.4554 / K:.4f}")
A, B = er(), er()
perm = list(range(N)); rng.shuffle(perm)
print(" p theory: single pair simulated: q = 1 q = 0.5 q = 0.2")
for p in (0.90, 0.80, 0.70, 0.65, 0.62, 0.60, 0.50, 0.40, 0.30):
sims = []
for q in (1.0, 0.5, 0.2):
partner = [perm[v] if rng.random() < q else None for v in range(N)]
sims.append(mutual(A, B, partner, p))
print(f" {p:.2f} {theory_single(p):.3f} {theory_pair(p):.3f}"
f" {sims[0]:.3f} {sims[1]:.3f} {sims[2]:.3f}")
# theory: single network p_c = 0.250; coupled pair p_c = 0.6139
# p theory: single pair simulated: q = 1 q = 0.5 q = 0.2
# 0.90 0.873 0.838 0.837 0.857 0.867
# 0.80 0.762 0.709 0.689 0.733 0.752
# 0.70 0.647 0.558 0.560 0.626 0.648
# 0.65 0.588 0.460 0.482 0.584 0.591
# 0.62 0.552 0.369 0.359 0.536 0.540
# 0.60 0.527 0.000 0.000 0.498 0.513
# 0.50 0.398 0.000 0.000 0.362 0.399
# 0.40 0.257 0.000 0.000 0.212 0.249
# 0.30 0.094 0.000 0.000 0.017 0.066A single network’s giant component vanishes continuously at : with 60 % of nodes kept, 52.7 % are still connected. With complete one-to-one dependence the collapse comes much earlier and much more abruptly: ; with 62 % of nodes kept, 36.9 % are still working (35.9 % in the simulation), and with 60 % kept, none. Losing 2 % more of the nodes takes the system from a third working to complete paralysis. With weaker dependence the picture changes back: with , 49.8 % are still working when 60 % are kept, and with the result is almost that of a single network. Parshani, Buldyrev and Havlin showed that reducing the coupling strength changes the transition from first to second order (Parshani et al. 2010).
Evidence
The benefits and costs of interconnection. Brummitt, D’Souza and Leicht studied sandpile cascades of load on two sparsely interconnected networks (including networks derived from two power grids in the south-eastern United States): a little interconnection lets one network absorb the other’s excess load, sharply reducing the chance of a large cascade; but beyond an optimal level (about 7.5 % in their idealised random networks) more links make large cascades likelier again; and interconnecting to suppress one’s own large cascades can enlarge the largest cascades of the system as a whole (Brummitt et al. 2012).
So “interdependence makes systems fragile” and “interconnection makes them robust” each hold only under certain conditions: the former depends on strong one-to-one dependence and the rule “outside the giant component means failure”, the latter on moderate connections that can share load. Real infrastructures are usually partly dependent, spatially structured, provided with back-up power and subject to human intervention. Parshani and colleagues’ result also shows that whether a collapse is “abrupt” can itself be changed by design: with fewer strong dependencies the collapse becomes gradual, giving people time to notice and intervene half-way.
Chapter summary
In the capacity–load model, the more uneven the load, the more easily the failure of one key node brings the network down: in a 300-node scale-free network, 10 % spare capacity is enough for random faults, but withstanding an attack on the highest-load node takes about 140 %. The most important redundancy looks most like waste in ordinary times. Two one-to-one interdependent random networks collapse completely and suddenly when about 61 % of nodes are kept, while a single network vanishes continuously only at 25 %; with weaker dependence the collapse becomes continuous again. All these conclusions rest on explicit model assumptions.
References
Fan, Y. (2026). Phase Transitions, Critical Slowing Down and Resilience in Complex Dynamical Systems: From Saddle-Node Bifurcations and Early-Warning Signals to Cascading Failures, Read Beside Classical Chinese Thought on Incipient Change [复杂系统相变、临界慢化与生态韧性的非线性动力学] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23770082 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).