Impact of self-healing capability on network robustness

A wide spectrum of real-life systems ranging from neurons to botnets display spontaneous recovery ability. Using the generating function formalism applied to static uncorrelated random networks with arbitrary degree distributions, the microscopic mechanism underlying the depreciation-recovery process is characterized and the effect of varying self-healing capability on network robustness is revealed. It is found that the self-healing capability of nodes has a profound impact on the phase transition in the emergence of percolating clusters, and that salient difference exists in upholding network integrity under random failures and intentional attacks. The results provide a theoretical framework for quantitatively understanding the self-healing phenomenon in varied complex systems.

Figure 1

Main panels: percolation threshold $q_c$ for networks of ${10}^6$ nodes from numerical simulations with $\alpha =0$ (squares), $0.5$ (circles), and 1 (triangles), and exact solutions (solid lines) by (5): (a) for ER graphs with $\langle k\rangle =\lambda$, and (b) for scale-free networks with degree exponent $\gamma =2.4$ and exponential cutoff $\kappa$. To obtain the data points $q_c$, we begin with $q=0.99$ and mark each node of a given network as recovered with probability $1-q$ independently, and delete all its incident edges (while we record its neighbor set). We then reconnect a random $\alpha$ fraction of intact neighbors for each recovered node [32]. After checking all nodes, we calculate the fraction (relative size) $S$ of the giant cluster. We decrease $q$ and repeat the process until $S<{10}^{-3}$. The plots correspond to the average of 50 random graphs with 20 independent runs for each. Insets: ${\alpha }_c$ vs $q_c$ by (5): (a) for ER graphs with $\lambda =5,10,15$, and (b) for scale-free networks with $\gamma =2.4$ and $\kappa =30,60,90$.

Figure 2

First row [(a) and (b)] main panels: fractions of giant clusters $S$ as functions of $q$ for $\alpha =0$ (squares), $0.5$ (circles), 1 (triangles), and ${\alpha }^I\left(\Delta \right)$ (crosses), and ${\alpha }^D\left(\delta \right)$ (pluses). Panel (a) is for ER graphs with $\lambda =10$; (b) is for scale-free networks with $\gamma =2.4$ and $\kappa =60$. The insets show, respectively, $S$ vs $f$, the fraction of the least connected nodes that are kept intact. Data points correspond to the simulation results averaged over 50 random graphs with 20 independent runs for each, and solid lines are the exact solutions using (6), (9), (10), and (11). Second row [(c) and (d)]: robustness $R$ of networks with different self-healing schemes under random failures and targeted attacks: (c) corresponds to (a), and (d) corresponds to (b).

Figure 3

Illustration of several different self-healing capability distributions. For ${\alpha }^I\left(k_c\right)$, the capability increases with respect to node degree, while for ${\alpha }^D\left(k_c\right)$, the capability decreases with respect to node degree. Moreover, ${\alpha }^I\left(k_c\right)$ with $k_c=\delta$ is equivalent to ${\alpha }^D\left(k_c\right)$ with $k_c=\Delta$—they are both equivalent to the uniform self-healing scheme ${\alpha }_k\equiv \alpha =1$.