Roni Parshani

We study a system composed from two interdependent networks A and B, where a fraction of the nodes in network A depends on nodes of network B and a fraction of the nodes in network B depends on nodes of network A. Because of the coupling between the networks, when nodes in one network fail they cause dependent nodes in the other network to also fail. This invokes an iterative cascade of failures in both networks. When a critical fraction of nodes fail, the iterative process results in a percolation phase transition that completely fragments both networks. We show both analytically and numerically that reducing the coupling between the networks leads to a change from a first order percolation phase transition to a second order percolation transition at a critical point. The scaling of the percolation order parameter near the critical point is characterized by the critical exponent β=1.

Current network models assume one type of links to define the relations between the network entities. However, many real networks can only be correctly described using two different types of relations. Connectivity links that enable the nodes to function cooperatively as a network and dependency links that bind the failure of one network element to the failure of other network elements. Here we present an analytical framework for studying the robustness of networks that include both connectivity and dependency links. We show that a synergy exists between the failure of connectivity and dependency links that leads to an iterative process of cascading failures that has a devastating effect on the network stability. We present exact analytical results for the dramatic change in the network behavior when introducing dependency links. For a high density of dependency links, the network disintegrates in a form of a first-order phase transition, whereas for a low density of dependency links, the network disintegrates in a second-order transition. Moreover, opposed to networks containing only connectivity links where a broader degree distribution results in a more robust network, when both types of links are present a broad degree distribution leads to higher vulnerability.

We derive an analytical expression for the critical infection rate r{c} of the susceptible-infectious-susceptible (SIS) disease spreading model on random networks. To obtain r{c}, we first calculate the probability of reinfection π, defined as the probability of a node to reinfect the node that had earlier infected it. We then derive r{c} from π using percolation theory. We show that π is governed by two effects: (i) the requirement from an infecting node to recover prior to its reinfection, which depends on the SIS disease spreading parameters, and (ii) the competition between nodes that simultaneously try to reinfect the same ancestor, which depends on the network topology.

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\"os-R\'enyi (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}_{\ensuremath{\infty}}$ is given by ${P}_{\ensuremath{\infty}}={p}^{s\ensuremath{-}1}[1\ensuremath{-}\mathrm{exp}(\ensuremath{-}{\mathit{kpP}}_{\ensuremath{\infty}})]{}^{s}$, where $1\ensuremath{-}p$ is the initial fraction of removed nodes. Our general result coincides with the known Erd$\mathrm{o\ifmmode \ddot{}\else \"{}\fi{}}$s-R\'enyi equation for random networks for $s=1$. For networks with Poissonian distribution of dependency links we find that ${P}_{\ensuremath{\infty}}$ is given by ${P}_{\ensuremath{\infty}}={f}_{k,p}({P}_{\ensuremath{\infty}}){e}^{(\ensuremath{\langle}s\ensuremath{\rangle}\ensuremath{-}1)[{\mathit{pf}}_{k,p}({P}_{\ensuremath{\infty}})\ensuremath{-}1]}$, where ${f}_{k,p}({P}_{\ensuremath{\infty}})\ensuremath{\equiv}1\ensuremath{-}\mathrm{exp}(\ensuremath{-}{\mathit{kpP}}_{\ensuremath{\infty}})$ and $\ensuremath{\langle}s\ensuremath{\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.