Group percolation in interdependent networks

In many real network systems, nodes usually cooperate with each other and form groups to enhance their robustness to risks. This motivates us to study an alternative type of percolation, group percolation, in interdependent networks under attack. In this model, nodes belonging to the same group survive or fail together. We develop a theoretical framework for this group percolation and find that the formation of groups can improve the resilience of interdependent networks significantly. However, the percolation transition is always of first order, regardless of the distribution of group sizes. As an application, we map the interdependent networks with intersimilarity structures, which have attracted much attention recently, onto the group percolation and confirm the nonexistence of continuous phase transitions.

Figure 1

Demonstration of the group percolation model. Here networks $A_0$ and $B_0$ are the resultant networks after contracting randomly the nodes in networks $A$ and $B$ into supernodes, represented as dashed circles. We assume that networks $A_0$ and $B_0$ are fully interdependent with the same number of supernodes.

Figure 2

A schematic of a larger giant grouped component than the giant component on a single-layer network. The red lines represent links in the original regular node network. Blue nodes (blue rectangles) constitute the giant component of the regular node network. However, all regular nodes inside the grey dashed line belong to the giant grouped component, since the corresponding supernodes belong to the giant component of the contracted network of supernodes. This exemplifies the situation with a larger giant grouped component than the giant component due to node group combination.

Figure 3

(a) Transition point $r_c$ and the mutual giant grouped component size at $r_c$ (the jump size) as functions of $m$, with a supernode size distribution $Q(m,m)=1, m=1,2,\cdots ,10$. (b) The same with (a) but with $Q(1,m)=1, m=1,2,\cdots ,10$. Networks $A_0$ and $B_0$ are obtained from two ER networks $A$ and $B$ with $〈k_A〉=〈k_B〉=3$. Dashed-lines are theoretical predictions and symbols are simulation results. Network sizes vary for different $m$ values to keep the number of supernodes $N=5000$.

Figure 4

Demonstration of the special case of group percolation model where networks $A_0$ and $B_0$ have the same number of supernodes and every supernode in network $A_0$ is connected to a same sized supernode in network $B_0$ via a bidirectional dependency link.

Figure 5

Decomposition of networks ${\tilde{A}}^{\prime }$ and ${\tilde{B}}^{\prime }$ according to the overlapping links. Bidirectional dependency links are represented by dashed lines. Solid red lines are the common connectivity links while solid blue lines are uncommon connectivity links within each network. Network $C^{\prime }$ contains all the common connectivity links and nodes of networks $\widetilde{A^{\prime }}$ and $\widetilde{B^{\prime }}$. Networks $A^{\prime }$ and $B^{\prime }$ contain all the uncommon connectivity links and nodes of networks $\widetilde{A^{\prime }}$ and $\widetilde{B^{\prime }}$, respectively. The connectivity link between nodes $a_1$ and $a_2$ in network $\widetilde{A^{\prime }}$ and the connectivity link between nodes $b_1$ and $b_2$ in network $\widetilde{B^{\prime }}$ are common connectivity links because nodes $a_1$ and $a_2$ depend on nodes $b_1$ and $b_2$, respectively. In networks $A^{\prime }$ and $B^{\prime }$, all nodes that belong to the same connected component in $C^{\prime }$ are grouped, and then merged into a supernode (dashed-circles) in networks $A_0$ and $B_0$. Since node groups are defined in the same way in both networks, the interdependency links are still well defined between supernodes in $A_0$ and $B_0$.

Figure 6

(a) Percolation properties of networks $\tilde{A}$ and $\tilde{B}$ under random regular node removal when networks $A, B$, and $C$ are all ER networks. Note that simulation results (colored symbols) for $P_{\infty }^{\tilde{A}}$ (or $P_{\infty }^{\tilde{B}}$) agree well with theoretical predictions (dashed curves). Here $k_A=k_B=3$, and $k_C=0,0.5,1.5$ with $\tilde{N}={10}^4$. (b) The number of iteration (NOI) in the simulation as a function of $p$ for each case. NOI curves peak at the critical thresholds $p_c$ at which the first-order phase transition occurs.

Figure 7

$p_c$ and $P_{\infty }^{\tilde{A}}$ (or $P_{\infty }^{\tilde{B}}$) at $p_c$ as a function of $\frac{k_C}{k_A+k_C}$ in theory, where $A, B$, and $C$ are all ER networks. Here we increase $k_C$ from 0 to 3 while keeping the sum of $k_A$ and $k_C$ to be 3. Note as $\frac{k_C}{k_A+k_C}$ increases, $p_c$ and the jump size decrease correspondingly. Especially when $k_C=0$ (thus $k_A=3$) we obtain $p_c^I=\frac{2.4554}{k_A}$; when $k_C=3$ (thus $k_A=0$) we get $p_c^{II}=\frac{1}{k_C}$. These results are in agreement with previous studies [10, 31]

Figure 8

(a) Percolation properties of networks $\tilde{A}$ and $\tilde{B}$ where networks $A$ and $B$ are SF networks, and network $C$ is an ER network. Note that simulation results (colored symbols) for $P_{\infty }^{\tilde{A}}$ (or $P_{\infty }^{\tilde{B}}$) agree well with theoretical predictions (dashed curves). Here $k_{\text{min}}=2, k_{\text{max}}=50, \gamma =2.8$ for networks $A$ and $B$, and $k_C=0.5,1,1.2$ for network $C$, with system size $\tilde{N}={10}^4$. (b) The number of iteration (NOI) in the simulation as a function of $p$ for each case. NOI curves peak at the critical thresholds $p_c$ where first-order phase transitions occur.