Simple and efficient self-healing strategy for damaged complex networks

The process of destroying a complex network through node removal has been the subject of extensive interest and research. Node loss typically leaves the network disintegrated into many small and isolated clusters. Here we show that these clusters typically remain close to each other and we suggest a simple algorithm that is able to reverse the inflicted damage by restoring the network's functionality. After damage, each node decides independently whether to create a new link depending on the fraction of neighbors it has lost. In addition to relying only on local information, where nodes do not need knowledge of the global network status, we impose the additional constraint that new links should be as short as possible (i.e., that the new edge completes a shortest possible new cycle). We demonstrate that this self-healing method operates very efficiently, both in model and real networks. For example, after removing the most connected airports in the USA, the self-healing algorithm rejoined almost 90% of the surviving airports.

Figure 1

Cluster distance after damage. (a) A toy network. (b) A number of nodes are removed from the network. (c) The remaining clusters in the network. (d) We consider each cluster to be one unit. The distance between the clusters, $r_{\mathrm{sep}}$, is measured according to the distances of cluster nodes in the original network. (e) The change of intercluster distance, $r_{\mathrm{sep}}$, as a function of removed nodes, $p$, for model and real networks after random node removal. (f) The change of intercluster distance, $r_{\mathrm{sep}}$, as a function of removed nodes, $p$, for model and real networks after targeted node removal.

Figure 2

Demonstration of the self-healing algorithm. (a) The initial structure of a toy network. (b) Three nodes, indicated by green (light gray), are removed from the network along with all their links. (c) The nodes that have lost half or more of their neighbors (blue nodes, empty symbols) will seek new connections. (d) These nodes will choose to connect to a random surviving node, if its distance $r$ in the original A network is at most $r_{\max }$. Here we use $r_{\max }=2$. (e) (Left panel) Network of airport connections in USA. (Middle panel) A targeted attack removes the 20% most connected airport nodes, and results to a disconnected network. The removed nodes are shown in green (light gray). (Right panel) The nodes that have lost more than 50% of their neighbors (shown in blue, dark gray) try to establish new links within distance $r_{\max }=2$. The new links (red lines) restore the large-scale network connectivity.

Figure 3

Fraction of surviving nodes in the largest cluster as a function of the removed nodes, $p$. The panels correspond to: (a) Two-dimensional square lattice, (b) Erdos-Renyi network with average degree $\langle k\rangle =3$, (c) random scale-free network with degree exponent $\gamma =2.5$, and (d) random scale-free network with degree exponent $\gamma =3$. The network size in all cases was $N={10}^5$ nodes. Black (lower) lines indicate the cluster size $P_1\left(p\right)$, after the initial removal of nodes. The red (middle) lines represent the cluster size after the healing process, $P_2(p;0.75)$, where a node decides to search for new connections if it has lost at least $q_c=75\%$ of its original neighbors. The blue (upper) line shows the healed cluster size, $P_2(p;0.5)$, for a corresponding threshold of $q_c=50\%$. The healing distance in all cases is $r_{\max }=2$.

Figure 4

(a) Snapshots of the healing process in a square two-dimensional lattice, after removing $p=50\%$ of the nodes. The nodes that survived the attack are shown in gray color, with black nodes indicating the largest cluster after a fraction, $f_s$, of the surviving nodes have generated a new link. The healing links are shown in green (light gray on black nodes). (b) Evolution of the largest cluster size during healing, as a function of the percentage of surviving nodes, $f_s$, that establish a new link. From top to bottom, the fraction of removed nodes increases in steps of 0.1, from $p=0.1$ to $p=0.9$ (or to the value indicated on the plot). The starting point of each curve at $f_s=0$ corresponds to the largest cluster size immediately after the removal of $p$ nodes. The end point of each curve indicates the final cluster size after the end of the healing process.

Figure 5

How the largest cluster size changes after healing, $P_2\left(p\right)$, as a function of the largest cluster size before healing, $P_1\left(p\right)$. Results are presented for model and real-world networks. The percentage of nodes removed is represented by the color of a node, increasing from right to left from $p=0.1$ to $p=0.9$. Each scattered point corresponds to a different realization of the process in each network. The efficiency of the healing process is demonstrated by the fact that all the points tend to be far from the diagonal, which would indicate no improvement, and remain close to the maximum efficiency value of $P_2\left(p\right)=1$.

Figure 6

Fraction of the surviving nodes that successfully established new connections, $f_s$, as a function of the fraction of nodes, $f$, that attempted to establish new connections following the removal of a percentage $p$ of nodes. The value of $p$ increases from left to right. The points that are closer to the diagonal indicate a higher percentage of success.

Figure 7

Effect of the self-healing process on the network modularity, as a function of the removed nodes. The modularity at $p=0$ corresponds to the original network modularity. For $p>0$, we consider the modularity of the network after healing with $r_{\max }=2$.

Figure 8

(a) Top row: Comparison of the result for the self-healing algorithm (filled symbols) with adding the same number of links starting from random nodes (empty symbols). In both cases, $r_{\max }=2$. Bottom row: Comparison of the self-healing algorithm (continuous lines) with the random case (dashed lines), for different $r_{\max }$ values. From bottom to top: $r_{\max }$=2, 3, 4, and $\infty$. (b) Comparison of the largest cluster size after an intentional attack.