Percolation of interdependent networks with intersimilarity

Real data show that interdependent networks usually involve intersimilarity. Intersimilarity means that a pair of interdependent nodes have neighbors in both networks that are also interdependent [Parshani et al. Europhys. Lett. 92, 68002 (2010)]. For example, the coupled worldwide port network and the global airport network are intersimilar since many pairs of linked nodes (neighboring cities), by direct flights and direct shipping lines, exist in both networks. Nodes in both networks in the same city are regarded as interdependent. If two neighboring nodes in one network depend on neighboring nodes in the other network, we call these links common links. The fraction of common links in the system is a measure of intersimilarity. Previous simulation results of Parshani et al. suggest that intersimilarity has considerable effects on reducing the cascading failures; however, a theoretical understanding of this effect on the cascading process is currently missing. Here we map the cascading process with intersimilarity to a percolation of networks composed of components of common links and noncommon links. This transforms the percolation of intersimilar system to a regular percolation on a series of subnetworks, which can be solved analytically. We apply our analysis to the case where the network of common links is an Erdős-Rényi (ER) network with the average degree $K$, and the two networks of noncommon links are also ER networks. We show for a fully coupled pair of ER networks, that for any $K⩾0$, although the cascade is reduced with increasing $K$, the phase transition is still discontinuous. Our analysis can be generalized to any kind of interdependent random network systems.

Figure 1

Common links in the interdependent geographic worldwide port network and the global airport network system. In the coupled network system, we identify common links if neighboring nodes (cities with direct transportation lines) in one network are also neighbors in the other network. For clarity, in the figure, 200 nodes are randomly chosen, and only common links attached to these nodes are plotted as solid (red) lines. Cities are shown as (blue) dots. Because two types of nodes (ports and airports) approximately correspond to the same cities, we just use single dots to denote them in the worldwide map.

Figure 2

Decomposition of networks according to the common links. Dots in the upper plane are the nodes from network $A_0$ and those in the lower plane are the nodes from network $B_0$. Interdependent nodes are connected by dashed lines. Solid thick (red) lines are the common links, and other links are shown in solid thin lines. Network $C_0$ is composed of common links. ${\tilde{A}}_0$ and ${\tilde{B}}_0$ are the complementary networks with respect to $C_0$. $a_i$ and $a_j$ are linked nodes in network $A_0$; their interdependent counterparts $b_i$ and $b_j$ are also linked in network $B_0$. Thus the link is a common link and appears in network $C_0$.

Figure 3

A sketch of the method of dividing and contracting the system after the initial attack. (a) The remaining interdependent networks $A_0$ and $B_0$ right after the initial attack. Thick (red) lines are the common links. Other links are shown in (black) solid thin lines. Interdependent nodes are connected by dashed lines. (b) Nodes in the same component of $C_0$ are contracted. Nodes that are within one circle belong to the same component in network $C_0$. Because of the first principle we propose, all the nodes from one component either survive together or die together. Thus the component can be regarded as a super node (if survived). The links between nodes from different components are now links between the two components. (c) The contracted network is further decomposed into subnetworks according to the component size in $C_0$. For example, $A_0^{\prime \left(2\right)}$ is the collection of super nodes of component size 2 in $A_0$, etc.

Figure 4

The evolution during cascading failures of the giant component size of network $A$, ${\mu }_{An}$, for both the theory and simulations. Here, $a=b=3$, $K=0.8$, $N=100000$, and $M_{\text{max}}=50$. The (blue) full circles show eight realizations of simulations with total collapse at the critical threshold $p=p_c=0.5528$. The (red) dashed rectangles show the theoretical prediction for $p_c=0.551$.

Figure 5

Comparison of the simulation results (symbols) for ${\mu }_{\infty }$ (top figure) against the theoretical results (curves) when network $C_0$ is an ER network. Here, we choose $a=b=3$, $K=0.2,0.5,0.8$, and $N=100000$. We also show (bottom figure) the number of iterative failures (NOI) in the simulation for the same values of $K$. Usually the peak of NOI values indicates the value of the critical threshold at the first order phase transition [31]. We can see the excellent agreement between the theoretical and simulation results.

Figure 6

The dependence of the critical value $p_c$ on the average degree $K$ of common links for interdependent ER networks systems. The average degrees of networks $A_0$ and $B_0$ are $a=b=3$, and that of $C_0$ is $K$. The network size is $N=300000$, and the number of realizations in simulations is 100. The curve is the theoretical results (using $M_{\text{max}}=50$), and the (red) full circles are the corresponding simulation results.

Figure 7

The dependence of the size of the jump at the critical threshold of the first order phase transitions on the average degree $K$ of network $C_0$. The average degrees of networks $A_0$ and $B_0$ are $a=b=3$. The network size is $N=100000$, and the number of realizations in simulations is 100. The dashed curve is the theoretical result ($M=50$), and the (green) solid squares are the corresponding simulation results at the critical thresholds. From the shape of the curve, we can see that the size of the jump at the critical point does not reach 0 for a very large $K$, which strongly supports that if the two mutually depending networks are not identical, the phase transition is always discontinuous.