Cascading failures in scale-free interdependent networks

Large cascades are a common occurrence in many natural and engineered complex systems. In this paper we explore the propagation of cascades across networks using realistic network topologies, such as heterogeneous degree distributions, as well as intra- and interlayer degree correlations. We find that three properties, scale-free degree distribution, internal network assortativity, and cross-network hub-to-hub connections, are all necessary components to significantly reduce the size of large cascades in the Bak-Tang-Wiesenfeld sandpile model. We demonstrate that correlations present in the structure of the multilayer network influence the dynamical cascading process and can prevent failures from spreading across connected layers. These findings highlight the importance of internal and cross-network topology in optimizing robustness of interconnected systems.

Figure 1

Probability distribution of cascade size, $P\left(s\right)$ (red circles), and cascade area, $P\left(a\right)$ (blue triangles), for (a) a neutral and (b) an assortative scale-free network. The dashed line corresponds to the mean-field solution to the BTW model, where $P\left(s\right)$ scales as a power law with exponent $-3/2$. Overlap of two measures demonstrates that nodes typically fail once during each cascade. Network size is $N=5000$, the degree distribution scale-free exponent is $\gamma =3.00$ and the BTW dissipation parameter $f=0.01$.

Figure 2

Chance of toppling in a cascade of size $s$. Top four panels show chance of a node toppling in cascades of size: (a) $50<s<100$, (b) $100<s<500$, (c) $500<s<1000,$ and (d) $s>2500$. In a neutral network (red circles), nodes of various degree are approximately equally likely to participate in cascades of different sizes. In an assortative network (blue squares) high degree nodes topple frequently in large cascades and infrequently in small ones, while the reverse is true for low degree nodes. Bottom two panels illustrate chance that a link between two nodes is used in sand redistribution during a cascade. Adjacency matrices for (e) neutral scale-free network and (f) assortative network, where nodes in each figure are sorted from low degree (bottom left corner) to high degree (top right corner). Colors indicate the probability that, in a large cascade, a given link participates in sand redistribution. These panels further demonstrate that, in assortative networks, links connected to high degree nodes are more likely to participate in large cascades.

Figure 3

A corollary of the “$1/k$ ansatz” is that the probability for a degree-$k$ node to have $i$ grains of sand is constant and equal to $1/k$, as denoted by the dashed line. However, for $k$-regular networks, as well as neutral and assortative scale-free networks, behavior deviates strongly from this corollary. Degree-10 nodes (a) and degree-20 nodes (b) are more likely to have near-critical amounts of sand, and less likely to have low amounts of sand. Furthermore, nodes in assortative scale-free networks behave similarly to nodes in $k$-regular graphs of the same degree, while nodes in neutral scale-free networks show the strongest deviation from the $1/k$ ansatz, with loads skewed strongly towards critical capacity. Network size is $N=5000$ and the degree distribution scale-free exponent is $\gamma =3.00$.

Figure 4

Distribution of sand in and out of equilibrium; (a) degree-5, (b) degree-10, and (c) degree-20 nodes. Black lines are the equilibrium distribution, just before any sand is dropped. Red, blue, cyan and magenta lines correspond to the sand distribution among nodes that receive grains of sand over the course of large cascades, where $s>N/2$ nodes topple. As the cascade progresses (from early generations to later ones), the sand distribution approaches the $1/k$ corollary, and sand topples with probability $1/k$ in agreement with the ansatz. In the figures, the networks are neutral scale-free with $\gamma =3.00$ and size $N=5000$. Other topologies show similar behavior.

Figure 5

The probability of a large cascade for two coupled assortative scale-free networks versus the connectivity probability $p$. Interlayer connectivity has a strong impact on the BTW dynamics, with the hub-to-hub coupling resulting in a constant chance of cascading failures, while random coupling results in an increasing occurrence of large events. Each network has $N=5000$ and the dissipative parameter $f=0.01$.

Figure 6

The probability of a cascade greater than $N=5000$ versus inter-layer connectivity $p$. Shown are neutral networks with random and hub-to-hub coupling as well as assortative networks with random and hub-to-hub coupling.

Figure 7

The probability of a large cascade occurring in a system of two coupled neutral scale-free networks versus the connectivity probability, $p$. This probability is virtually indistinguishable between hub-to-hub and random interlayer connectivity. As the connectivity probability $p$ increases, cascading failures reach a constant. In each network, $N=5000$ and the dissipative parameter $f=0.01$.

Figure 8

Choice of the dissipation rate $f$ adopted in the sandpile dynamics affects the tail of the distribution of cascade sizes, $P\left(s\right)$. Inverse power law scaling that characterises $P\left(s\right)$ is preserved for (a) regular random graph, (b) neutral scale-free network, and (c) assortative scale-free network.

Figure 9

Probability that a degree-$k$ node holds $i$ grains of sand stays constant despite significant variation in the dissipation rate $f$ of the sandpile process. Behavior of a random 10-regular network is compared with $k=10$ nodes of a neutral and assortative scale-free network, respectively.

Figure 10

Probability that a degree-$k$ node holds $i$ grains of sand saturates as a network size $N$ increases. Behavior of a sandpile process on a random 10-regular network with dissipation rate (a) $f=0.01$ and (b) $f=0.001$ is shown.

Figure 11

Chance of large cascades occurring in a system of (a) neutral and (b) assortative interconnected scale-free networks, where scaling exponent of the individual layer degree distribution is $\gamma =2.50$. Despite differences in absolute probability values, qualitative behavior remains the same as for $\gamma =3.00$ (compare to Figs. 7 and 5).