Generalized model for $k$-core percolation and interdependent networks

Cascading failures in complex systems have been studied extensively using two different models: $k$-core percolation and interdependent networks. We combine the two models into a general model, solve it analytically, and validate our theoretical results through extensive simulations. We also study the complete phase diagram of the percolation transition as we tune the average local $k$-core threshold and the coupling between networks. We find that the phase diagram of the combined processes is very rich and includes novel features that do not appear in the models studying each of the processes separately. For example, the phase diagram consists of first- and second-order transition regions separated by two tricritical lines that merge and enclose a two-stage transition region. In the two-stage transition, the size of the giant component undergoes a first-order jump at a certain occupation probability followed by a continuous second-order transition at a lower occupation probability. Furthermore, at certain fixed interdependencies, the percolation transition changes from first-order $\to$ second-order $\to$ two-stage $\to$ first-order as the $k$-core threshold is increased. The analytic equations describing the phase boundaries of the two-stage transition region are set up, and the critical exponents for each type of transition are derived analytically.

Figure 1

Demonstration of an interdependent network with coupling $q=0.75$ with dependency links shown as dashed lines. The 2-core and 3-core are the highest possible $k$-core in the top and bottom layers, respectively, while still preserving all the dependency links.

Figure 2

Comparison of theory (lines) and simulation (symbols) for two coupled Erdős-Rényi networks at fixed average local threshold (a) $k=1.5$, (b) $k=2.0$, and (c) $k=2.5$. As the coupling $q$ is increased, $k$-core percolation transition changes from second-order to first-order. For $k=2.0$, a two-stage transition is seen at intermediate couplings. Simulation results agree well with the theory.

Figure 3

The giant component for two coupled Erdős-Rényi networks ($z_1=10$), computed numerically and through simulations, as a function of fraction of initially removed nodes $p_0$ at different average local threshold $k$ for couplings: (a) $q=0.3$, (b) $q=0.7$, (c) $q=0.8$, and (d) $q=0.9$. For low coupling $q=0.3$, the nature of $k$-core percolation is similar to that of single networks. For high couplings $q=0.8$ and $q=0.9, k$-core percolation is first-order, indicating the increased instability of the system compared to single networks. For the intermediate coupling $q=0.7, k$-core percolation is initially first-order for $k=1.5$, which then becomes a two-stage transition as the average local threshold is increased to $k=2.0$. The cascades during $k$-core percolation are expected to increase as the local threshold of nodes are increased, and therefore, $k$-core percolation would be (intuitively) expected to remain as first-order. Surprisingly, $k$-core percolation changes to second-order for $k=2.3$. Finally, the increased instability in the system is manifested into $k$-core percolation becoming a first-order transition for $k=2.7$. Simulation results (shown as symbols) are obtained for a system with ${10}^6$ nodes in each network.

Figure 4

Comparison between theory and simulation (symbols) of $k$-core percolation in two interdependent scale-free networks with exponent $\gamma =2.5$, with both layers having identical local thresholds $k=1,2,3$. Simulation results were obtained for a system with $N={10}^6$ nodes in each network. The minimum and maximum degree for nodes in each network were set to be $i_{\min }=2$ and $i_{\max }=1000$, respectively.

Figure 5

Comparison of behavior of the function $h_{k,q}\left(Z\right)$ for two coupled Erdős-Rényi networks at fixed average local threshold (a) $k=1.5$ and (b) $k=2.0$ at different couplings. As seen in the phase diagram (see Fig. 6), $k$-core percolation changes from a second-order at low couplings to a first-order at high couplings passing through a tricritical point for $k=1.5$, and through a two-stage transition for $k=2.0$. In both cases, $h_{k,q}\left(Z\right)$ is characterized by monotonically increasing behavior corresponding to second-order transition and, by the presence of a global minima corresponding to first-order transition. For $k=1.5$, the inflection point occurs at $Z=0$, which immediately turns into a global minima as the coupling is increased, leading to a tricritical point. For $k=2.0$, the inflection point occurs at $Z>0$, which turns into a local minima, leading to a two-stage transition, followed by being a global minima as the coupling is increased.

Figure 6

Complete phase diagram for $k$-core percolation transition for two interdependent Erdős-Rényi networks with average degree $z_1=10$. Both networks have the same average local threshold per site $k=(1-r)k_a+r(k_a+1)$, with fraction $1-r$ of randomly chosen nodes having local threshold $k_a$ and the remaining nodes having local threshold $k_a+1$. The symbol “X” in the phase diagram indicates the coupling $q_{c,2.5}$.

Figure 7

Plot of tricritical coupling $q_{\mathrm{tri},k}$ as a function average threshold $k$ obtained from the numerical solution of perturbative expansion to first order, second order and exact equation given in Eqs. (9) and (10). The numerical results are in excellent agreement with the simulation results (shown as symbols) for a network with ${10}^5$ nodes.

Figure 8

Numerical solution of the perturbative expansion of $q_{c,1}\left(k\right)$ and $q_{c,2}\left(k\right)$ around the triple point $q_{c2,.5}$ given in Eq. (15).

Figure 9

The critical exponents for the $k$-core percolation of coupled networks are given at different regions of the phase diagram for two interdependent Erdős-Rényi networks with average degree $z_1=10$. ${\beta }_1$ denotes the critical exponent for the first-order transition and near the abrupt jump of the two-stage transition. ${\beta }_2$ denotes the critical exponent for the second-order transition and at the continuous part of the two-stage transition. Regions labeled with both ${\beta }_1$ and ${\beta }_2$ represent the two-stage transition regime. The exponents are summarized in Eqs. (17) and (18). The symbol “X” in the phase diagram indicates the coupling $q_{c,2.5}$. The critical exponents of $k$-core percolation transitions for low couplings are identical to those found in single networks [26].

Figure 10

Percolation threshold $p_c$ as a function of (a) the coupling $q$ for fixed average local threshold $k=1.0,1.5,2.0,2.5$ representing horizontal lines in Fig. 6 and (b) the average local threshold $k$ for several fixed coupling $q=0.3,0.7,0.8,0.9$ representing vertical lines in Fig. 6. Dashed and continuous lines indicate that the percolation threshold is at abrupt (first-order) jump and continuous transition respectively. Simulation results (shown as symbols) are obtained for a system with ${10}^6$ nodes in each network.

Figure 11

Complete phase diagram for $k$-core percolation transition for two coupled random regular networks with coupling $q$. Both the networks have the same local $k$-core threshold distribution. A fraction $r$ of randomly chosen nodes have local threshold $k_a+1$ and remaining nodes have $k_a$, resulting in average local threshold $k=(1-r)k_a+r(k_a+1)$. The phase diagram has similar features that were seen in two coupled Erdős-Rényi networks (Fig. 6). The critical exponents for all the regions in the phase diagram are identical to that of Erdős-Rényi networks as reported in Sec. 2b. The expressions for critical percolation thresholds for continuous transition part of both second-order and two-stage transitions are given in Eq. (A1).