Targeted damage to interdependent networks

Complex systems consisting of interdependent subsystems may be represented by multilayer networks with interdependency links between layers. The giant mutually connected component (GMCC) of such an interdependent (or multiplex) network collapses with a discontinuous hybrid transition under random damage to the network. If the nodes to be damaged are selected in a targeted way, the collapse of the GMCC may occur significantly sooner. Understanding the limits of the resilience of such systems to targeted attacks is therefore an essential problem. Finding the minimal damage set which destroys the largest mutually connected component of a given interdependent network is a computationally prohibitive simultaneous optimization problem. We introduce a simple heuristic strategy—effective multiplex degree—for targeted attack on interdependent networks that leverages the indirect damage inherent in multiplex networks to achieve a damage set smaller than that found by any existing noncomputationally intensive algorithm. We show that the intuition from single-layer networks that decycling (damage of the 2-core) is the most effective way to destroy the giant component does not carry over to interdependent networks and in fact such approaches are worse than simply removing the highest degree nodes.

Figure 1

(a) An example of a (fully) interdependent two-layer network. (b) The mutually connected components present in this network. (c) The multiplex representation of the same network with (d) the mutually connected components.

Figure 2

A small grouping of nodes within the GMCC (LMCC) of a two-layer multiplex. Infinity symbols indicate a connection leading to an infinite GMCC subtree (or the LMCC 2-core in a finite system) in a given layer. Two or more such connections correspond to membership of the GMCC 2-core of that layer. Nodes 1, 2, 5, and 6 belong to the 2-core within the GMCC in the layer with dashed (blue) edges. Nodes 1, 2, and 4 belong to the 2-core of the solid (red) edged layer. Since nodes 1 and 2 belong to the 2-core of the GMCC in both layers they cannot be removed in an avalanche. Nodes 3–6 are outside one or both 2-cores and are therefore in a critical state, potentially being removed in an avalanche of propagating damage. For example, removal of node 2 will lead to the removal of all four of these nodes. Damage propagates along critical edges in the directions marked by arrows.

Figure 3

Progression of the relative size $S$ of the LMCC with a fraction $p$ of the nodes removed under different targeted attack strategies for a duplex network of two uncorrelated Erdős-Rényi layers with mean degree $\mu =5$ and $N={10}^5$. From right to left: random damage (dashed, black), collective influence ${\mathtt{CIp}}_{\mathtt{S}}$ (green), CoreHDs (solid blue), CoreHD1 (dashed blue), highest degree sum DegSum (purple), and product DegProd (dashed purple), Effective multiplex degree (EMD) (red). Also shown are the approximate effective multiplex degree results obtained using only one and two iterations of Eq. (2). The inset: Results for $N={10}^4$, allowing comparison with simulated annealing, marked by the arrow.

Figure 4

The absolute difference between damaging fraction $p_c\left(t\right)$ obtained by limiting to $k$ iterations of Eq. (2) and final value $p_c$, for two fully interdependent Erdős-Rényi layers with mean degree $\mu =5$ and $N={10}^5$ nodes, averaged over ten realizations (circles, red). Initial value $t=0$ corresponds to highest degree sum strategy. Also shown are progressions for partially interdependent networks, $f=0.6$ (squares) and $f=0.3$ (triangles).

Figure 5

Results for the relative number of nodes removed in destruction of the LMCC for two Erdős-Rényi layers, both with varying mean degree $\mu$. (a) Values of $\mu$ from 3 to 8 and (b) $\mu$ from 9 to 25. All networks consist of $N=10000$ nodes. The networks are fully interdependent, and the two layers are uncorrelated. All results were averaged over ten realizations, except for simulated annealing (SA), which was a single realization.

Figure 6

Collapse threshold $p_c$ for different attack strategies for (a) two uncorrelated Erdős-Rényi layers with different mean degrees. One layer has fixed mean degree ${\mu }_1=5$, whereas the other has mean degree ${\mu }_2$ and (b) two power-law degree distributed layers $P\left(q\right)\propto q^{-\gamma }$ as a function of power-law exponent $\gamma$. Each layer has $N=10000$, ten realizations, except simulated annealing, one realization.

Figure 7

Results for the relative number of nodes removed in destruction of the LMCC for (a) two scale-free layers, both with mean degree 10, one with exponent ${\gamma }_1=2.5$, the other with varying exponent ${\gamma }_2$ and (b) An Erdős-Rényi layer and a scale-free layer both with mean degree 10 and varying degree distribution exponent $\gamma$. In this case the CoreHD1 algorithm was modified to always attack the scale-free layer.

Figure 8

(a) The multiplex representation of a partially interdependent two-layer network. Interdependent nodes are shown as open circles, and noninterdependent nodes are shown as closed circles. In (b) we show the mutually connected components present in this network. Note that noninterdependent nodes may belong to more than one MCC.

Figure 9

Comparison of collapse threshold $p_c$ as a function of interdependent node fraction $f$ for different targeted attack strategies for a duplex network of two uncorrelated Erdős-Rényi layers with mean degree $\mu =5$ and $N=10000$, averaged over 50 realizations. Simulated annealing results were averaged over five realization.