The combined effect of connectivity and dependency links on percolation of networks

Abstract

Percolation theory is extensively studied in statistical physics and mathematics with applications in diverse fields. However, the research is focused on systems with only one type of links, connectivity links. We review a recently developed mathematical framework for analyzing percolation properties of realistic scenarios of networks having links of two types, connectivity and dependency links. This formalism was applied to study Erd$\ddot{o}$s-R$\acute{e}$nyi (ER) networks that include also dependency links. For an ER network with average degree $k$ that is composed of 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 (-kp{P}_{\infty }){]}^s$ where $1-p$ is the initial fraction of randomly removed nodes. Here, we apply the formalism to the study of random-regular (RR) networks and find a formula for the size of the giant component in the percolation process: $P_{\infty }=p^{s-1}(1-r^k{)}^s$ where $r$ is the solution of $r=p^s(r^{k-1}-1)(1-r^k)+1$. These general results coincide, for $s=1$, with the known equations for percolation in ER and RR networks respectively without dependency links. In contrast to $s=1$, where the percolation transition is second order, for $s>1$ it is of first order. Comparing the percolation behavior of ER and RR networks we find a remarkable difference regarding their resilience. We show, analytically and numerically, that in ER networks with low connectivity degree or large dependency clusters, removal of even a finite number (zero fraction) of the network nodes will trigger a cascade of failures that fragments the whole network. This result is in contrast to RR networks where such cascades and full fragmentation can be triggered only by removal of a finite fraction of nodes in the network.

11 pages, 3 figures

References in corpus (7)

• Spatial Networks
• Mitigation of Malicious Attacks on Networks
• Robustness of interdependent networks under targeted attack
• Cascade of failures in coupled network systems with multiple support-dependent relations
• The critical effect of dependency groups on the function of networks
• Percolation in Interdependent and Interconnected Networks: Abrupt Change from Second to First Order Transition
• Percolation in networks composed of connectivity and dependency links

Cited by in corpus (9)

• Multilayer Networks
• Percolation on complex networks: Theory and application
• Robustness of a Tree-like Network of Interdependent Networks
• Spatially localized attacks on interdependent networks: the existence of a finite critical attack size
• Resilience of Networks Formed of Interdependent Modular Networks
• Robustness of a Network Formed of Spatially Embedded Networks
• Cascading failures in coupled networks with both inner-dependency and inter-dependency links
• Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
• Enhanced robustness of single-layer networks with redundant dependencies