Percolation of networks with directed dependency links

The self-consistent probabilistic approach has proven itself powerful in studying the percolation behavior of interdependent or multiplex networks without tracking the percolation process through each cascading step. In order to understand how directed dependency links impact criticality, we employ this approach to study the percolation properties of networks with both undirected connectivity links and directed dependency links. We find that when a random network with a given degree distribution undergoes a second-order phase transition, the critical point and the unstable regime surrounding the second-order phase transition regime are determined by the proportion of nodes that do not depend on any other nodes. Moreover, we also find that the triple point and the boundary between first- and second-order transitions are determined by the proportion of nodes that depend on no more than one node. This implies that it is maybe general for multiplex network systems, some important properties of phase transitions can be determined only by a few parameters. We illustrate our findings using Erdős-Rényi networks.

Figure 1

Demonstration of the synergy between the percolation process and the dependency process that leads to a cascade of failures. The network contains two types of links: connectivity links (solid black lines) and directed dependency links (dashed red arrows). (a)$\to$(b) Initial failure: a random node is removed. (c)$\to$(e) Synergy between percolation process and dependency process: nodes cutoff from the giant component or depending on failed nodes are removed. (f) Steady state: the surviving giant component contains four nodes.

Figure 2

The size of the giant component $P_{\infty }\left(p\right)$, as a function of the fraction of nodes that remain after random removal, $p$, for ER networks with $\langle k\rangle =8$ and $D\left(z\right)=Q\left(0\right)+Q\left(1\right)z+Q\left(2\right)z^2$. The symbols represent simulation results of ${10}^4$ nodes and the dashed lines show the theoretical predictions from Eq. (10). The percolation threshold $p_c^{II}$ is uniquely determined by $Q\left(0\right)$.

Figure 3

The size of the giant component $P_{\infty }\left(p\right)$ as a function of the fraction of nodes that remain after random removal, $p$, for ER networks. Here we used $D\left(z\right)=Q\left(0\right)+Q\left(1\right)z$ with $\langle k\rangle =5$ ($\square$ and $☆$) and $D\left(z\right)=Q\left(0\right)+Q\left(1\right)z+Q\left(2\right)z^2$ with $\langle k\rangle =10$ ($◯$ and $▿$). The symbols represent simulation results of ${10}^4$ nodes and the dashed lines are the theoretical predictions from Eq. (10). With a relatively larger $Q\left(0\right)$, the network undergoes a second-order phase transition at $p_c^{II}$, which only depends on $Q\left(0\right)$. However, for relatively smaller $Q\left(0\right)$ and larger $Q\left(1\right)$ and $Q\left(2\right)$, the network undergoes a first-order phase transition.

Figure 4

Comparison between simulation (symbols) and theory (lines) for $P_{\infty }\left(p_c\right)$ as a function of $Q\left(1\right)$ for different $D\left(z\right)$ ($D\left(z\right)=Q\left(0\right)+Q\left(1\right)z+Q\left(2\right)z^2+Q\left(3\right)z^3$) while keeping $Q\left(0\right)+Q\left(1\right)=0.9$ and $\langle k\rangle =10$. At the first-order phase transition point $p_c^I,P_{\infty }\left(p_c\right)$ is nonzero; whereas at the second-order phase transition point $p_c^{II}$ and $P_{\infty }\left(p_c\right)$ is zero. From Eq. (19) the boundary between first-order phase transition and second-order phase transition is only dependent on $Q\left(0\right)+Q\left(1\right)$, thus at $Q{\left(1\right)}_c=0.75$ for this case.

Figure 5

The fraction of nodes that have one dependent node $Q\left(1\right)$ as a function of the average degree $\langle k\rangle$ with $Q\left(0\right)+Q\left(1\right)=\frac{9}{10}$. The dashed lines are theoretical results obtained from Eqs. (20) (green) and (21) (red) with intersection points at $(\frac{2}{2M-1},\frac{1}{2})$. The dashed blue line is the boundary between first-order phase transition and unstable system, obtained numerically. Here the dashed red and green lines only depend on $m_0$, whereas the blue lines (both solid and dashed) depend on the specific details of $Q\left(k_o\right)$ other than $M$.