Percolation in networks composed of connectivity and dependency links

Networks composed from both connectivity and dependency links were found to be more vulnerable compared to classical networks with only connectivity links. Their percolation transition is usually of a first order compared to the second-order transition found in classical networks. We analytically analyze the effect of different distributions of dependencies links on the robustness of networks. For a random Erdös-Rényi (ER) network with average degree $k$ that is divided into dependency clusters of size $s$, the fraction of nodes that belong to the giant component $P_{\infty }$ is given by $P_{\infty }=p^{s-1}[1-\exp (-{\mathit{kpP}}_{\infty })]{}^s$, where $1-p$ is the initial fraction of removed nodes. Our general result coincides with the known Erd$\mathrm{ö}$s-Rényi equation for random networks for $s=1$. For networks with Poissonian distribution of dependency links we find that $P_{\infty }$ is given by $P_{\infty }=f_{k,p}(P_{\infty })e^{(\langle s\rangle -1)[{\mathit{pf}}_{k,p}(P_{\infty })-1]}$, where $f_{k,p}(P_{\infty })\equiv 1-\exp (-{\mathit{kpP}}_{\infty })$ and $\langle s\rangle$ is the mean value of the size of dependency clusters. For networks with Gaussian distribution of dependency links we show how the average and width of the distribution affect the robustness of the networks.

Figure 1

Connectivity network with dependency clusters. The edges represent connectivity relations, while the (blue, red, and green) groups surrounded by curves represent dependency relations between all the nodes of the same group (color). The dependency relations can be between very $"\mathit{far}$” nodes in the connectivity network. In the general case, the sizes of each dependency clusters follow a given distribution.

Figure 2

(a) The size of the giant cluster, ${\varphi }_{\infty }\equiv P_{\infty }p$, vs $p$, the fraction of nodes that remain after random removal, for ER networks ($k=8$) for different fixed sizes of dependency clusters $s$. The symbols represent simulation results of systems of $50000$ nodes, and the solid lines show the theoretical predictions. For the case of $s=1$, there are no dependency clusters, and the regular percolation process leads to second-order phase transition. For $s⩾2$, a first-order phase transition characterizes the percolation process represented by discontinuity of $P_{\infty }$ at $p_c$. Both the regular and the new first-order percolation obey Eq. (15). (b) The number of iterative failures (NOI) sharply increases when approaching the critical threshold $p_c$ for the first-order transitions, and thus, they represent a useful method for identifying accurately the value of $p_c$ [15]. Each curve is maximal as its related curve in (a) approaches the critical threshold from both sides.

Figure 3

Theory [Eq. (18), dashed lines] and simulation results (symbols) are compared for the values of $p_c$ for ER networks with different average degree $k$ and different fixed sizes of dependency clusters $s$. The solid symbols, for $s=1,$ represent the known Erdös-Rényi second-order phase transition threshold for a network without dependency relations, while the open symbols represent first-order phase transition thresholds.

Figure 4

The minimum averaged degree $k_{\text{min}}$ as a function of the (fixed) size of dependency clusters $s$. The solid line shows the theoretical results, obtained from Eqs. (17) and (22). The region of $s$ and $k$ values below the line represents an unstable network that will collapse after any single node failure. For $k$ and $s$ values above the line, the network is stable, and there exists $p_c<1$.

Figure 5

(a) The size of the giant cluster, ${\varphi }_{\infty }\equiv P_{\infty }p$, vs $p$ (solid lines) and ${\varphi }_{\infty }(p_c)$ (symbols) for ER networks with average degree $k=15$ and dependency clusters normally distributed around averaged size $\langle s\rangle =4$. The different curves represent different standard deviations $\sigma$ [$\sigma =0$ (solid triangle), $\sigma =0.8$ (circle), $\sigma =1.6$ (square), $\sigma =2.4$ (open triangle), and $\sigma =3.2$ (diamond)]. (b) Theory (solid lines) and simulation (symbols) values of $p_c$ for ER networks with average degree $k=15$ and dependency clusters normally distributed around averaged size $\langle s\rangle$ vs the width of the distribution $\sigma$. The three curves represent different values of $\langle s\rangle$: $\langle s\rangle =4$ (circles), $\langle s\rangle =6$ (squares), and $\langle s\rangle =10$ (triangles). For $\sigma \to 0$ (solid symbols) the Gaussian distribution becomes a $\delta$ function with fixed size of dependency clusters, and thus, $p_c$ is identical to those obtained by Eqs. (17) and (18) for groups of single size $s$.

Figure 6

The size of the giant cluster, ${\varphi }_{\infty }\equiv P_{\infty }p$, vs $p$ for ER networks ($k=8$) and Poisson distribution of dependency clusters with different average sizes $\langle s\rangle$. The symbols represent simulation results of systems of $50\hspace{0.5em}000$ nodes, and the solid lines show the theoretical predictions. For $\langle s\rangle =1$ and $2$ the network undergoes a second-order transition, while for $\langle s\rangle =2.5,3.5$, and $5$ the network undergoes a first-order transition [see Fig. 7, where the exact transition point from first- to second-order transition is shown].

Figure 7

(a) Theory (lines) and simulations (symbols) are compared for the values of $p_c^I(\langle s\rangle )$ and $p_c^{\mathit{II}}(\langle s\rangle )$ for ER networks with different average degree $k$ (circles for $k=3$, triangles for $k=5$, and squares for $k=8$). For $\langle s\rangle >\langle s\rangle {}_c$ (dashed line) the network undergoes a first-order transition. The theoretical values of the transition point $p_c^I(\langle s\rangle )$ that are calculated according to Eq. (29) are compared with simulations (open symbols) performed using the NOI method (explained in text). For $\langle s\rangle <\langle s\rangle {}_c$ the network undergoes a second-order transition, and the theoretical values of the transition point $p_c^{\mathit{II}}(\langle s\rangle )$ that are calculated according to Eq. (28) are compared with simulations (solid symbols) performed using the second-largest cluster method. The dashed line separating the first and second orders is obtained according to Eq. (32). (b) The size of the giant cluster ${\varphi }_{\infty }$ above the critical point $p_c$ is described by ${\varphi }_{\infty }(p)-{\varphi }_{\infty }(p_c)~(p-p_c){}^{\beta }$, as shown in the inset. The critical exponent $\beta$ above the transition point $p_c$ is plotted vs the average size of the dependency clusters $\langle s\rangle$ for a network with $k=8$ [compare to (a); squares]. For the region of the second-order transition, $\langle s\rangle <\langle s\rangle {}_c$, we find $\beta =1$ ($\langle s\rangle {}_c$ is marked by the vertical dashed line), while for the region of the first-order transition, $\langle s\rangle >\langle s\rangle {}_c$, $\beta =1/2$.