Enhanced robustness of single-layer networks with redundant dependencies

Dependency links in single-layer networks offer a convenient way of modeling nonlocal percolation effects in networked systems where certain pairs of nodes are only able to function together. We study the percolation properties of the weak variant of this model: Nodes with dependency neighbors may continue to function if at least one of their dependency neighbors is active. We show that this relaxation of the dependency rule allows for more robust structures and a rich variety of critical phenomena, as percolation is not determined strictly by finite dependency clusters. We study Erdős-Rényi and random scale-free networks with an underlying Erdős-Rényi network of dependency links. We identify a special “cusp” point above which the system is always stable, irrespective of the density of dependency links. We find continuous and discontinuous hybrid percolation transitions, separated by a tricritical point for Erdős-Rényi networks. For scale-free networks with a finite degree cutoff we observe the appearance of a critical point and corresponding double transitions in a certain range of the degree distribution exponent. We show that at a special point in the parameter space, where the critical point emerges, the giant viable cluster has the unusual critical singularity $S-S_c\propto {(p-p_c)}^{1/4}$. We study the robustness of networks where connectivity degrees and dependency degrees are correlated and find that scale-free networks are able to retain their high resilience for strong enough positive correlation, i.e., when hubs are protected by greater redundancy.

Figure 1

Example of a simple network with dependencies consisting of two connected components (in the standard percolation sense). Solid black lines represent connectivity links, and dashed blue lines represent dependency links. Strongly and weakly dependent components (of the same network) are shown on the right.

Figure 2

Phase diagrams of (a) Erdős-Rényi and (b) scale-free connectivity networks with mean connectivity degree $z_c$, both with an Erdős-Rényi dependency network of mean degree $z_d$. The scale-free connectivity network is an uncorrelated random network with a degree distribution of the form $P_c\left(k\right)\sim {(k+B)}^{-\gamma }$, with lower and upper degree cutoffs $k_{\text{min}}=1$ and $k_{\text{max}}=1000$, respectively. The parameter $B$ was chosen to achieve a given mean degree $z_c$. The degree distribution exponent was $\gamma =3$. The phase separation curves were obtained by numerical analysis of the self-consistency equations presented in Sec. 3.

Figure 3

(a) Relative size $S$ of the GWDC as a function of mean dependency degree $z_d$, where both the connectivity and dependency networks are Erdős-Rényi networks. Curves are shown for four different values of the mean connectivity degree $z_c$. Open circles represent simulation results, and solid lines correspond to the numerical solution of Eqs. (8) and (9). (The number of nodes was $N={10}^6$ in all cases and results were averaged over 100 realizations.) (b) Phase diagram of the same network class, with $S$ overlaid as a color map. Solid and dashed black lines correspond to continuous and discontinuous transitions, respectively. The tricritical point and cusp point (see Secs. 4a and 4b) are marked by a solid red circle and solid blue square, respectively.

Figure 4

(a) Function $f\left(x\right)$ (scaled to be at the critical threshold) for different values of the mean dependency degree $z_d$. (b) Relative size $S$ of the GWDC as a function of connectivity link activation probability $p$, for different values of $z_d$. The three curves on each panel correspond to a continuous transition ($z_d=0.2$), the tricritical point ($z_d=0.3517$), and a discontinuous transition ($z_d=0.5$). The mean connectivity degree is $z_c=3$ in all cases. Both the connectivity and the dependency network is Erdős-Rényi.

Figure 5

(a) The maximum (with respect to $x$) of the function $f(x,z_d)$, as a function of $z_d$, for three different values of $z_c$. (b) The relative size $S$ of the GWDC as a function of $z_d$ for the same three values of $z_c$ as in (a). The three curves in each panel correspond to a case with two discontinuous transitions with $S=0$ in between ($z_c=1.847$), the cusp point ($z_c=1.848$), and a situation with no transitions ($z_c=1.849$). Both the connectivity and the dependency network are Erdős-Rényi.

Figure 6

(a) Phase diagram for a scale-free connectivity network ($z_c=3$, $\gamma =3$, $k_{\text{min}}=1$, $k_{\text{max}}=1000$) and the Erdős-Rényi dependency network. The solid line represents continuous transitions, and the dashed line corresponds to discontinuous transitions. The shaded green region indicates double percolation transitions. (b) Function $f\left(x\right)$ (scaled to be at the critical threshold) for different values of the mean dependency degree $z_d$. (c) Relative size $S$ of the GWDC as a function of connectivity link activation probability $p$, for different values of $z_d$. The four curves on (b) and (c) correspond to the critical point ($z_d=1.896$), a double transition ($z_d=1.95$), the point where continuous transitions disappear ($z_d=2.155$), and a discontinuous transition ($z_d=2.25$).

Figure 7

(a) Phase diagrams for scale-free connectivity networks ($z_c=3$, $k_{\text{min}}=1$, $k_{\text{max}}=1000$) for different values of the degree distribution exponent $\gamma$. Continuous transitions are represented by solid lines and discontinuous ones by dashed lines. A critical point and double transitions appear for intermediate values of $\gamma$, while there is a smooth switch (at a tricritical point) between continuous and discontinuous transitions for low and high $\gamma$ values. (b), (c) Parts of two phase diagrams zoomed in from (a): (b) $\gamma =4.5$ and (c) $\gamma =2.2$. In (b) and (c) nonphysical solutions of Eqs. (8) and (9) are also shown.

Figure 8

Appearance of the second maximum of the function $f\left(x\right)$ for scale-free networks ($z_c=3$, $k_{\text{min}}=1$, $k_{\text{max}}=1000$). (a) and (c) show the appearance of the second maximum at $x=0$ $[\gamma =6.1$, $z_d=0.888$, and $z_d=0.889$ for (a) and (c), respectively]. (b) and (d) show the appearance of the second maximum at some $x>0$ $[\gamma =2.15$, $z_d=3.357$, and $z_d=3.359$ for (b) and (d), respectively].

Figure 9

Map of the different types of phase transitions occurring in a model of random scale-free connectivity network coupled with an Erdős-Rényi dependency network. The scale-free connectivity network had a degree distribution of the form of Eq. (14), the parameter $B$ always adjusted to achieve a mean connectivity degree of $z_c=3$. The green (blue) region corresponds to a single continuous (discontinuous) transition. The yellow (red) region corresponds to a double transition of the type “continuous–discontinuous” (“discontinuous–discontinuous”). The point marked with a green triangle corresponds to the conditions (16) and the critical behavior (17). The right panel is a zoomed-in version of the framed rectangular area of the left panel.

Figure 10

Phase diagrams for the model of correlated connectivity and dependency degrees defined by the distribution (18). The percolation threshold values $p_c$ were determined by numerical analysis of Eqs. (21) and (22). The mean connectivity degree was $z_c=3$ for all networks. For scale-free connectivity networks the degree distribution (14) was used, with degree cutoff values $k_{\text{min}}=1$ and $k_{\text{max}}=1000$. [For the dependency degree distributions the cutoff values were changed to $k_{\text{min}}=0$ and $k_{\text{max}}=1200$, because in the model described by Eq. (18) a dependency degree equal to zero is possible and also the biggest dependency degree may be slightly greater than the biggest connectivity degree.]