You are an expert at summarizing long articles. Proceed to summarize the following text: 
a property of critical importance for complex networks is their resilience to damage or attack @xcite . one fascinating demonstration of the underlying complexity of these systems is that compromise in structure can be substantial even after the loss of a very small number of nodes @xcite . the repercussions to the network from this structural compromise can be immense , usually resulting in complete loss of communication among the surviving nodes and therefore a complete destruction of the intended network functionality . because of the obvious importance for practical applications , the robustness of a network s structure to damage has continuously remained the focus of intensive research in the network science literature @xcite . even though we now have a thorough understanding of complex network disintegration , the inverse process of ` healing ' a network is much less understood . is there a direct relationship between healing structural features and restoring function ? what does it really take for a network to restore its functionality after losing some of its nodes ? while there are various types of healing , one realistic approach is to consider the case in which disabled nodes have been permanently removed and can not be resurrected , but the surviving nodes can still generate new links to other surviving nodes . of course , a node could trivially create as many new links as possible , but in many realistic settings the cost and time associated with establishing a new link can be high . we then need to optimize the network functionality given the constraints of rebuilding costs @xcite . as a natural first case , we explore the scenario in which optimal network functionality is achieved under the structural condition that all the nodes are connected in one large cluster . in this way , every node can reach any other node in the network , even if the connecting path may be long . this reflects systems such as communication networks @xcite electrical grids @xcite , air traffic @xcite and shipping routes @xcite , etc . additional requirements can be imposed , for example the maximum path between any two nodes can be bounded @xcite , or entirely different cases for structure and function can be explored ( e.g. function is optimized when the network structure has a particular degree distribution , or is highly modular , etc . ) , but as a first approach our only metric here is the size of the largest cluster .      a basic , but fundamental insight is that healing can be employed with one of two possible goals in mind . the first goal can be to fix the structure in a way that the topology remains as close to the original network as possible . for example , descriptions of some social groups have revealed particular degree distributions and one natural inclination in healing a damaged social network might be to restore edges by focusing on this aspect of repair . however , degree distribution itself is unlikely to support social function . for features such as social identity or support from a close group of friends , the structural features of modularity and clustering are more important . therefore , if we are attempting repair in order to restore function , we may decide to ignore entirely the impact to degree distribution from repair , instead adding back links that restore ( for example ) local clustering coefficient . since damage can alter both structural and functional features , it is easy to consider repairing structure since regaining initial structure should provide restored initial function . critically , however , it may not be that one and only one structural feature can support the original function . the main question is therefore to discover efficient strategies that can restore network functionality through the addition of new links . in a recent work , redundant ( dormant ) links were considered to be activated after damage and it was shown that they can restore functionality in infrastructure trees @xcite . similarly , healing in interdependent networks was shown to prevent cascading failures @xcite . in a different approach , nodes were allowed to spontaneously recover and become active again , leading to an interesting behavior of phase - flipping where the network switches between high - activity and low - activity modes @xcite . under different definitions of network function in which a global minimum traffic flow must be maintained and each node has a particular flow capacity that must be redistributed in case of damage , the network functionality can be restored by mitigation strategies @xcite . one critical and under - discussed feature of damage , especially in inhomogeneous complex networks , is that the impact from the loss of a single link on overall function can differ drastically depending on where that link occurs in the local and global structure . loss of a single link that uniquely connects two otherwise disconnected components of a network will have a greater impact to functions ( such as the one we study ) that rely on the size of the largest cluster than would the loss of one of the three links that make up a triangle . while obvious , it is nevertheless important and profound that we consider healing as a process that should focus on areas of the network in which the most damage has been done to the function , rather than to the structure . in the case of our largest connected component example , this means we should focus more effort towards creating new edges that restore connectivity to nodes that are most direly impacted in their ability to relay messages .      phrased in this way , it may seem as though the only option is to analyze global network structure in order to understand which nodes are most critical to restoring function . such a global algorithm could potentially locate the optimal solution by mapping the current state of the network and adding only the links that are missing to restore functionality . however , this centralized planning may not always be feasible , since it may cost a lot in terms of advance planning , communication between the central authority and the individual nodes , the time that it takes to transmit all relevant information , the possibility that communication takes place through the network itself and the central node may have been functionally disconnected from this critical communication , as well as any combination of the above factors which may limit the ability of constructing one central plan and communicate it to all the surviving nodes . luckily , there is no need for this type of centralized global analysis . we proceed to propose a self - organizing healing algorithm that exploits this heterogeneity feature of damage while relying only on local information accessible to each node , and with low cost from the construction of new links . since one of our goals will be to limit the amount of centralized information that will be necessary before repair to the network can begin , we propose purely local definitions of damage that can be assessed by each node . to make this distinction clearly , in this work optimal ` healing ' will refer to adding new links so that every node can reach any other node in the system , and the term ` self - healing ' indicates that individual nodes decide on their own whether they need to create new links or not .      we here demonstrate that our self - healing model can restore connectivity function very efficiently in two different ways . firstly , we show effective restoration of function with the creation of very few new links relative to the number lost to damage . we demonstrate the effectiveness of the method through the size of the healed largest component , the number of nodes that need to form new links , and the changes in modularity compared to the original network . we further show this is true even if we impose cost constraints on the length of new links ( i.e. the number of links in the shortest path required to connect the two nodes without the addition of the new link ) . secondly , we show that a null healing model ( in which the same number of links are constructed randomly ) achieves a drastically lesser restoration of function . we analyze the efficiency of our self - healing algorithm over various network topologies and in cases of both random - node - removal damage and when damage is targeted to affect only specific , high - structural - impact nodes . based on this ` uneven damage to function ' perspective , we show that relatively inexpensive , rapid healing may be relatively easy to achieve , even in the absence of global information .    to formalize the problem , we consider the simplest possible case of an isolated complex network which undergoes a loss of a fraction of its nodes , resulting in a possible loss of large - scale connectivity . to mitigate this loss of function , each node can then generate one new link in an attempt to restore connectivity . as mentioned above , this is a trivial problem without any additional constraints because connecting to random nodes would result in a structure similar to an erdos - renyi network . in our work , we study what conditions are necessary and sufficient to restore connectivity under the constraints that : a ) establishing a new link is costly and that cost is borne by the node initiating the link , b ) the new links are as short as possible ( based on the path distances of the undamaged network ) , and c ) the decision is purely local , so that a node does not know anything about the network state , except for its own neighborhood . we show that these conditions can be easily met through a simple local - decision algorithm , based on the number of surviving neighbors . there is no need to transfer any information between nodes , and the only requirement is that a node can know if a neighbor within a given distance remains alive or not . the first step in identifying efficient healing algorithms is to determine the state of the network immediately after the removal process . this topic has not received attention in the existing literature , which instead mainly focuses only on the properties of the largest connected cluster . for the purpose of a healing algorithm , we consider all the clusters that remain in the system after a fraction @xmath0 of system nodes have been removed . a possible measure that can quantify the extent of damage is the minimum distance between these clusters , @xmath1 , which we define as the minimum possible distance from a node in the cluster to any other node in any other cluster . since all clusters are disconnected , this distance is calculated in terms of the original network . in practice , we renormalize the damaged structure in the following way ( fig .  [ fig1]a - d ) : every cluster is substituted by one super - node . all these super - nodes are obviously isolated . we restore all the removed nodes and links among them . the links that were connecting removed nodes with any node contributing to a super - node result in a link between the super - node and the removed node ( we also remove any double links ) . in this renormalized network , we can then calculate how close the super - nodes are to each other . obviously , this distance is bounded by the minimum value of @xmath2 . notice also that this distance is different from the distance between a random node in the cluster and other clusters , since it is solely determined by the one node in the cluster which is closest to another cluster . ( color online ) 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 , @xmath1 , is measured according to the distances of cluster nodes in the original network . ( e ) the change of inter - cluster distance , @xmath1 , as a function of removed nodes , @xmath0 , for model and real networks after random node removal . ( f ) the change of inter - cluster distance , @xmath1 , as a function of removed nodes , @xmath0 , for model and real networks after targeted node removal . ]    intuitively , the inter - cluster distance is small in centralized networks and is large in sparse , extended networks . for example , in a star network where all nodes are connected to a central node , the distance @xmath1 can never be larger than 2 independent of how many nodes we remove . in a one - dimensional lattice this distance can become very large , especially when @xmath0 becomes large and the gap among surviving clusters increases rapidly . our focus on inter - cluster distance is to enable estimation of the most efficient length for the healing links . if , for example , typical inter - cluster distances were @xmath3 then it would be pointless to add links much shorter than that . similarly , since one of our goals is to minimize the cost , calculating @xmath1 allows us to avoid constructing unnecessarily long links . we studied the two typical cases of node removal in complex networks : random removal and targeted attack . in fig . [ fig1]e we show the average @xmath4 over all clusters as a function of the fraction of randomly removed nodes , @xmath0 . in model networks , such as the two - dimensional square lattice , erdos - renyi , and scale - free networks , the value of @xmath5 remains close to 2 until roughly @xmath6 . when we remove a larger percentage of the nodes the inter - cluster distance increases up to @xmath7 . in real networks , on the other hand , the average distance never increases significantly , independently of the value of @xmath0 .    in targeted attacks we remove the nodes in decreasing order of their degree . as expected , the targeted attack leads to increasing damage and consequently the inter - cluster distance increases in most of the networks ( fig . [ fig1]f ) , with the exceptions of the email network and the square lattice . the email network includes many strong hubs and , as a consequence , node distances are very short , which also reflects on the inter - cluster distances . for lattices , a targeted attack is the same as random removal , because the degree distribution is a delta function . since er networks also have a narrow degree distribution , one might expect that the inter - cluster distance in er networks would also be independent of the attack strategy . in fig . [ fig1 ] , we find that the opposite is true . the average distance @xmath8 increases rapidly after @xmath6 , and at @xmath9 it reaches the highest value we observed , @xmath10 . this is a result of the absence of hubs . when the majority of the highest - connected nodes have been removed , the small remaining clusters consist only of low degree nodes , which have a low probability of being close to each other since there are no hubs to centralize the network . so , in general , we observe that the isolated clusters are relatively close to each other , and the inter - cluster distances remain for the largest part close to the minimum value of @xmath11 , at least for random removals , while in very few cases does it reach @xmath12 or more under targeted attacks . the basic idea of the self - healing method is that each node monitors the fraction , @xmath13 , of its neighbors that remain alive . if this fraction falls below a given threshold @xmath14 , e.g. @xmath14=50% , then the neighbor attempts to establish a new link . this link can be at a maximum distance of @xmath15 , where distances are always measured as path length in the original network . if there is no node within this distance , then the node abandons its attempt to build a new connection . importantly , in agreement with the above findings on inter - cluster distance , we show that even if the maximum distance is the smallest possible , i.e. @xmath15=2 , large - scale connectivity is still restored even though the node has no information about whether or not the new link will connect to the largest cluster , or even if it will connect to a different cluster than the one it currently belongs to . this process can be dynamic , so that nodes do not even need to be aware that there is an attack , as long as they can monitor how many of their links lead to live nodes , in which case they can respond immediately and attempt to create a new link . this real - time healing is more effective than if the nodes can only attempt to heal once an attack is completed ( e.g. surprise attacks , or cases in which new link construction is risky until an attack has concluded ) and obviates the need for rigorous definitions of global attacks vs local damage . here , we show that the self - healing algorithm is efficient , even in this worst - case scenario , where the nodes do not have the capacity to respond until the attack is over . ( color online ) 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 which 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 @xmath16 in the original a network is at most @xmath15 . here we use @xmath17 . ( 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 @xmath17 . the new links ( red lines ) restore the large - scale network connectivity . ] the order parameter , which quantifies the large - scale connectivity , is the fraction of the live nodes that belong in the largest connected component , denoted by @xmath18 after the attack , and by @xmath19 after the healing process . the implementation of this model includes three steps ( fig . [ fig2]a - d ) , which are as follows :    1 . a fraction @xmath0 of the @xmath20 nodes initially in the system is removed from the network . the size of the remaining largest connected cluster , @xmath18 , is expressed as a fraction of the remaining nodes . 2 .   each of the remaining nodes decides independently if it needs a new link , depending on whether the fraction of its remaining neighbors @xmath21 exceeds a given threshold @xmath14 ( for any given node , @xmath22 is the number of neighbors after damage , and @xmath23 is the original number of neighbors of this node ) . we denote the fraction of the surviving nodes that need healing , i.e. those whose degree has fallen below the threshold , as @xmath24 . 3 .   these @xmath25 nodes attempt to find a new neighbor within a distance @xmath15 . if such a neighbor is found , the nodes establish the new link . the fraction of nodes that succeed to establish a new link is @xmath26 . these new links then result to a new large cluster that includes a fraction of @xmath27 [ @xmath28 nodes . the size of the largest cluster , @xmath18 , indicates the extent of damage to the structure immediately after the nodes removal . a value close to @xmath29 means that the remaining nodes are isolated in small clusters and they can not access each other . the plot of @xmath18 as a function of @xmath0 represents the well - studied percolation process of the largest cluster as we increase the number of removed nodes . the plot of @xmath30 can be used to estimate the efficiency of the healing process . after the self - healing process , the largest cluster becomes @xmath31 , since we have added links in the structure . the difference between the two sizes is a measure of the process success .      as a real - world example , we can demonstrate how the airport network in usa can be influenced by attacks and healing ( fig . [ fig2]e ) . the unperturbed network ( left panel ) is quite dense and contains a large number of connections , condensed in many hub nodes . after an intentional attack on 20% of the most connected nodes ( middle panel ) , 80% of the nodes are still functional but are barely connected to other nodes , since most of the traffic was directed through the hubs . the original network contains 332 nodes , so after the removal of 66 nodes we are left with 266 nodes . the largest cluster size connects only 30 of these nodes ( @xmath32 ) , and the surviving nodes are either completely isolated or belong to very small clusters . after we apply the self - healing algorithm ( right panel ) , the connectivity is restored and the largest cluster grows to 235 nodes ( @xmath33 ) . of course , the network becomes less centralized as hubs are removed and local connections are added during healing , so that the network topology changes , but the important part is that the functionality is restored and the network becomes navigable again . now , it is possible to reach practically any node , independently of the origin . in this example it is also easy to see that the new connections have to remain close to the healing node , since the cost of long - range connections may be prohibitively high . the most interesting cases are those where the damage destroys the large - scale connectivity ( i.e. @xmath18 tends to 0 ) . the question now becomes how easy it is to bring @xmath30 as close to 1 as possible . therefore , the main quantities to compare are the values of @xmath34 vs @xmath35 . an ideal process would correspond to a plot of values as close to the horizontal @xmath36 line as possible . this means that , independent of the initial damage , the self - healing process guarantees complete connectivity . the worst - case scenario , on the other hand , is a @xmath37 line along the diagonal , indicating that there is no benefit from the self - healing process .    in fig . [ fig3 ] we show the evolution of @xmath18 and @xmath19 as a function of the removed percentage of nodes , p , in a random removal process . the results for lattices , erdos - renyi , and scale - free networks are well known and we recover the typical curves for @xmath18 @xcite . the self - healing process results in significantly larger critical points for lattice and er networks . this delay indicates that even though a network has been fully disintegrated , our healing algorithm can reconstitute one large cluster of size @xmath19 among the surviving nodes . this improvement is obvious even for large threshold values , such as @xmath14=0.75 , when a node delays adding a new link until it has lost more than 75% of its neighbors . as we relax this threshold to @xmath14=0.5 the largest cluster reaches higher values over a wider @xmath0 interval . lowering this threshold even more did not produce noticeable improvement . therefore , in the following analysis we fix this value to @xmath14=0.5 . ( color online ) fraction of surviving nodes in the largest cluster as a function of the removed nodes , @xmath0 . the panels correspond to : ( a ) two - dimensional square lattice , ( b ) erdos - renyi network with average degree @xmath38 , ( c ) random scale - free network with degree exponent @xmath39 , and ( d ) random scale - free network with degree exponent @xmath40 . the network size in all cases was @xmath41 nodes . black ( lower ) lines indicate the cluster size @xmath18 , after the initial removal of nodes . the red ( middle ) lines represent the cluster size after the healing process , @xmath42 , where a node decides to search for new connections if it has lost at least @xmath43 of its original neighbors . the blue ( upper ) line shows the healed cluster size , @xmath44 , for a corresponding threshold of @xmath45 . the healing distance in all cases is @xmath17 . ] each node seeks new connections within a maximum distance @xmath15 , and for the results seen in fig . [ fig3 ] we used the minimum possible distance , i.e. @xmath15=2 . as we increase the radius of possible new connections the connectivity becomes easier to achieve for a number of reasons . first , there are more options because the node can create a link , even if all second - neighbors have been removed . second , the effect of long - range shortcuts is known to favor large - scale connectivity @xcite . for example , if the attack results in small , isolated clusters , then short - range shortcuts will tend to remain within the same cluster and can not assist in bridging between different clusters . on the other hand , long - range shortcuts will have a much higher probability of bridging otherwise unconnected parts of the network because they can choose nodes that are far from the immediate neighborhood of their initiator @xcite . the problem with this approach , of course , is that the associated cost of long links may become significantly higher . it is important , therefore , to know if the minimum possible cost is enough to restore the network structure .      as we will demonstrate below , in the absence of cost restrictions , higher values of @xmath15 improve the repair results , with the optimum case being that @xmath15 is unrestricted and the node can randomly choose any other surviving node in the system this is a trivial theoretical result , because long - range links can connect isolated clusters which are far from each other in case of extended damage . importantly , however , beyond this trivial result , we show that the minimum value of @xmath15=2 is already sufficient to restore network structure . we therefore focus our discussion by reporting only results for this worst - case scenario . ( color online ) ( a ) snapshots of the healing process in a square two - dimensional lattice , after removing @xmath46 of the nodes . the nodes that survived the attack are shown in gray color , with black nodes indicating the largest cluster after a fraction , @xmath47 , 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 , @xmath47 , that establish a new link . from top to bottom , the fraction of removed nodes increases in steps of 0.1 , from @xmath48 to @xmath9 ( or to the value indicated on the plot ) . the starting point of each curve at @xmath49 corresponds to the largest cluster size immediately after the removal of @xmath0 nodes . the end point of each curve indicates the final cluster size after the end of the healing process . ]    in fig . [ fig4 ] we present many examples of the self - healing process , for both model and real - world networks . a lattice structure offers the simplest example of self - healing . in fig . [ fig4]a we present a toy example , in a lattice where @xmath46 of the nodes have been removed . as we add the links to a fraction fs of the nodes that have lost more than half of their neighbors , the size of the largest cluster increases and presents essentially a typical second order percolation transition . this behavior is verified in the first panel of fig . [ fig4]b , where the large - scale connectivity is easily restored for values of @xmath50 . the second - order transition is observed in all the model networks , but only when the values of @xmath0 reach close to their critical values pc . for @xmath51 , the initial largest cluster at @xmath49 extends over a non - zero fraction of the remaining nodes and , notably , there is no transition in these cases . the linear increase of the largest cluster size indicates that the new links attach small clusters to the spanning cluster , and there is never any other cluster of significant size . the absence of a transition is observed in all real networks , even when the initial largest cluster is very small . for instance , at @xmath9 , the largest cluster size of the co - authorship network starts at less than @xmath52 and with healing it increases almost linearly up to @xmath53 . notice that in these plots the process does not necessarily go up to @xmath54 , since not all nodes need , or can find , new connections according to the rules of the algorithm . we then compare the value of the cluster size at the end of healing , @xmath34 , with the cluster size before healing , @xmath35 , for different values of @xmath0 ( fig . [ fig5 ] ) . in lattices , we know that close to the threshold @xmath55 the system is in the critical phase so that a small number of links are enough to restore connectivity . however , in the plot we can see the large improvement that healing brings to the tolerance of the system . even though the network disintegrates very rapidly as we remove more nodes and increase @xmath0 to @xmath56 , the largest cluster after self - healing practically includes all remaining nodes , so that @xmath57 . moving from @xmath58 to @xmath59 causes a much greater damage which can not be restored via our self - healing process and @xmath34 abruptly drops to @xmath60 . in practice , the self - healing algorithm has managed to delay the location of the critical point from @xmath55 to @xmath61 . this simple behavior of either a fully connected or fully disconnected cluster is rather idiosyncratic of the highly organized configuration of nodes in the lattice , which is not found in random models and real - world networks , as we show below . ( color online ) how the largest cluster size changes after healing , @xmath19 , as a function of the largest cluster size before healing , @xmath18 . 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 @xmath48 to @xmath9 . 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 @xmath62 . ] the erdos - renyi network ( with average degree @xmath38 ) follows a similar pattern where removing 70% of the nodes results to isolated clusters , @xmath63 . after healing with our algorithm the largest cluster size encompasses a large part of the remaining nodes , @xmath64 . this striking difference indicates that the remaining clusters remain close to criticality and relatively close to each other , since they can be merged when nodes add new local links with @xmath15=2 . similar improvement is found for the case of scale - free networks with different degree exponents . an important difference between random model networks and real - world networks is usually the level of organization . for instance , typical empirical networks exhibit higher degrees of clustering and modularity , features that are missing in the randomly built networks @xcite . nevertheless , this organization can potentially drastically impact the outcome of the healing process . in the examples that we studied ( fig .  [ fig5 ] ) we see that self - healing is equally , if not more , efficient in restoring the largest cluster in empirical networks . in certain cases , e.g. the friendship social network in irvine or the email exchange network , practically all the surviving nodes belong to the same cluster after healing , even though the starting network state is highly disintegrated , i.e. @xmath65 . of particular importance is the result for the network of airport connections , because it is a spatially embedded structure and we can approximate spatial distance with network distance , at least to demonstrate the principle that longer jumps may be very costly to implement . the example highlights the importance of small @xmath15 values . if an airport closes down then the traffic needs to be redirected to another airport in the general area , but it is impractical if this distance remains unrestricted . additionally , in this example connectivity is crucial for the network to be functional ( one needs to be able to reach any destination ) . under the conditions of our self - healing algorithm , the large - scale connectivity was almost certain in all our simulations , with more than 80% of the nodes belonging in the largest cluster . the large fluctuations , especially in the extreme case where 90% of the nodes have been removed , are the result of the small network size , which includes 332 nodes . this demonstrates that healing may become unpredictable for very small networks , where one or two links may be enough to connect the small number of clusters . the percentage of nodes that find themselves with fewer neighbors than the threshold increases with the number of nodes that are removed . these nodes do not necessarily manage to find a new neighbor within the distance @xmath15=2 , either because all these nodes have been removed or because there is already a connection . as we show in fig . [ fig6 ] , all nodes in lattice and in model random networks manage to find a new neighbor as long as less than 50% of the initial nodes have been removed . as the extent of damage increases , a larger percentage of nodes need new connections , but less than half of those manage to do that . on the contrary , in real networks all nodes manage to find new connections almost independently of the extent of damage in the network . ( color online ) fraction of the surviving nodes that successfully established new connections , @xmath47 , as a function of the fraction of nodes , @xmath24 , that attempted to establish new connections following the removal of a percentage @xmath0 of nodes . the value of @xmath0 increases from left to right . the points that are closer to the diagonal indicate a higher percentage of success . ] even though functionality is restored , since the majority of nodes can now communicate with each other through the structural repair that reconnected a large cluster , it is not clear what impact restoration of this particular structural feature may have on other topological / structural features . we therefore study the effect on the modularity of the healed network compared to the modularity of the undamaged network as an example of a potentially important structural feature which is not necessarily correlated to the size of the largest cluster . we use the standard definition for modularity @xmath66 , as the fraction of links between modules , minus the expected number of links within these modules for a random graph with the same node degree distribution @xcite . for fig . [ fig6 ] we report the maximum possible value of @xmath66 , using the algorithm from ref . @xcite . in fig . [ fig7 ] we show changes in modularity after a random removal of @xmath67 nodes and the application of the self - healing algorithm . a common trend in both model and real networks is that modularity increases considerably with increasing @xmath0 . this shows that the healing effect tends to create significantly stronger modules , and nodes tend to become more connected within the same network area . of course , this is the result of the short - range links in the presented simulations , where @xmath15=2 . in practice , the healing algorithm replaces the links that are removed with local links , enhancing thus the modular character of the network . the only instances where modularity decreases are at large values of @xmath0 in the model networks . this result can be explained by fig . [ fig6 ] where only a small percentage of nodes manage to find new connections and therefore the form of the resulting structure is not very different than the damaged structure . ( color online ) effect of the self - healing process on the network modularity , as a function of the removed nodes . the modularity at @xmath68 corresponds to the original network modularity . for @xmath69 , we consider the modularity of the network after healing with @xmath17 . ]      the efficiency of our method can be tested against a random insertion of links under a similar set of constraints , as for the self - healing algorithm . for example , we can add the same number of links at the same distance , but random nodes are chosen to create new links , rather than those who have lost most of their neighbors . in this way , we can detect if the crucial factor is the number of edges or the particular features of the nodes that select to establish new connections . even if our model results did not exceed those of random insertion , our method is based on a self - organized algorithm that provides a simple local decision scheme , where there is no need for a central authority to coordinate actions around the network . still , we demonstrate below that our method , which we tested in a number of model and real - world networks , significantly exceeds the results of random decisions . we assess the effectiveness of the algorithm by comparing our results to such a null model . in this way , we can determine if there is a benefit to choosing which nodes create new links based on @xmath14 . for each realization of nodes removal with the self - healing algorithm we calculated how many new links were introduced in the system , resulting to @xmath19 . we then added the same number of links to the damaged network , but this time the link originated from a random node instead of the node that had lost more than a fraction @xmath45 of its neighbors . these new links were established within a distance @xmath15=2 , so that the total cost remained the same in both cases . the result in the top row of fig . [ fig8]a shows that the self - healing algorithm performed better in all cases compared to this null model . the reason is that when a random node decides to establish a new link , it is possible that many of its neighbors still survive and the new link does not bring together isolated parts of the network . this is also why when the removed percentage of nodes is small , e.g. 10 - 20% , there is no increase in the largest cluster size , unless we use the nodes that have lost most of their neighbors . we also studied the effect of @xmath15 on the results ( fig . [ fig8 ] ) . as expected , we find that as we increase the maximum distance for new connections , the repair process becomes more efficient . as shown in the plot for the self - healing algorithm , @xmath70 is already enough to completely restore connectivity among all the remaining nodes , practically under any conditions . the optimal case is found for @xmath71 . the results for the random model are consistently inferior to those of our algorithm . the trend of better healing with increasing @xmath15 remains , but now even for unrestricted @xmath72 , the value of the repaired largest cluster can not reach the optimal value , @xmath62 .     ( 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 , bottom row : comparison of the self - healing algorithm ( continuous lines ) with the random case ( dashed lines ) , for different @xmath15 values . from bottom to top : @xmath15=2 , 3 , 4 , and @xmath73 . ( b ) comparison of the largest cluster size after an intentional attack . ]      until now , we studied the healing process on networks where the nodes were randomly selected for removal . another important removal technique simulates intentional attack on the network , where nodes are removed in descending order of their degree , i.e. the highest connected nodes are removed first . this attack requires a much smaller percentage of removed nodes to destroy the network , since all the hubs that glue the network together are removed and the network disintegrates into small pieces . the self - healing algorithm is efficient in this case , too ( fig . [ fig8]b ) . the critical value of @xmath0 for a scale - free network with degree exponent @xmath74=2.5 moves from @xmath75 to @xmath55 . this is a huge difference that allows the network to operate even after losing the most connected nodes in its backbone . similarly , in the case of the airport connection network , the removal of the hubs leads to a disconnected network when 20% of the nodes are removed , but the healed network manages to preserve the largest cluster even if more than 60% of the nodes are removed . in this paper we make explicit a fundamental feature of damage in complex networks and use it to design a very simple self - healing algorithm to restore connectivity - based function . we show that even just this simple example is enough to restore large - scale connectivity in a severely damaged network , while keeping the reconnection cost low . in this particular scenario of structure enabling function , a node decides based on its own link losses to add a new link to one of its second neighbors ( provided at least one survives ) without considering any other parameter . this approach has the added benefit that it is strictly local , and every node can make the decision autonomously . the cost is also lower with this strategy compared to selecting random nodes for the same number of links . the critical insight that working to restore function may not rely on restoring the initial structure allowed us to design a threshold , @xmath14 . this threshold acts as a natural filter to direct the addition of the links towards the areas where function has been most affected by the damage in this connectivity - based scenario . in fact , this strategy represents a worse - case scenario , because the nodes make new connections only after the removal of all nodes , or equivalently if the attack takes place faster than the nodes can react . in an alternate version , the algorithm could be applied in a dynamic fashion so that a node continuously monitors its neighbors and decides to add new links based on current information , i.e. as soon as it notices that the number of its neighbors falls below the threshold . under this scenario , a node could establish more than one new links during the process and it would be easier to preserve long - range connectivity , simply because of the addition of a larger number of links . what we showed above is that this extension is not necessary since a similar result can be achieved with much fewer new connections . a few interesting parallels can be drawn between the self - healing algorithm and achlioptas processes @xcite . in the latter , we start from an empty network of @xmath20 nodes which grows by adding new links according to the process rules . these rules can either favor or discourage the emergence of a largest cluster . in our case , the starting point is an already fractioned network , and the goal is to merge all clusters into one giant network with as few links as possible . a key difference is that we only use local decisions , while in typical achlioptas processes the information of the involved cluster sizes is required . we thank the dept .  of homeland security for funds in support of this research through the ccicada center at rutgers , and nsf easm grant no .  1049088 . we analyzed four different networks , based on the following datasets :    1 . email network : email messages sent at the computer sciences department of london s global university http://lisgi1.engr.ccny.cuny.edu/~makse/social/emailcontacts.dat.gz . cond - mat co - authorship : the network of co - authorship in preprints submitted to the cond - mat section of arxiv.org @xcite . irvine social network : the dataset was downloaded from http://toreopsahl.com/datasets/#online_social_network and has been analyzed in @xcite . it includes online messages sent among students at the university of california , irvine , through a facebook - like social network . usa airport network : a link indicates that two networks are connected by a direct flight . this dataset refers to flights in 1997 and can be downloaded at http://vlado.fmf.uni-lj.si/pub/networks/data/mix/usair97.net . r. cohen , k. erez , d. ben - avraham , and s. havlin , _ phys . lett . _ * 85 * , 4626 ( 2000 ) . r. albert , h. jeong , and a. l. barabasi , _ nature _ * 406 * , 378 ( 2000 ) . s. boccaletti , v. latora , y. moreno , m. chavez , and d. hwang , _ phys . rep . _ * 424 * , 175 ( 2006 ) . d. helbing , _ nature _ * 497 * , 51 ( 2013 ) . d. j. watts , _ proc . natl . sci . _ * 99 * , 5766 ( 2002 ) . r. cohen , k. erez , d. ben - avraham , and s. havlin , _ phys . _ * 86 * , 3682 ( 2001 ) . d. s. callaway , m. e. j. newman , s. h. strogatz , and d. j. watts , _ phys . lett . _ * 85 * , 5468 ( 2000 ) . a. a. moreira , j. s. andrade jr . , h. j. herrmann , and j. o. indekeu , _ phys . lett . _ * 102 * , 018701 ( 2009 ) . c. moore , g. ghoshal , and m. e. j. newman , _ phys . e _ * 74 * , 036121 ( 2006 ) . n. farid and k. christensen , _ new j. phys . _ * 8 * , 212 ( 2006 ) . j. saldana , _ phys . e _ * 75 * , 027102 ( 2007 ) . c. m. schneider , l. de archangelis , and h. j. herrmann , _ europhys . lett . _ * 95 * , 16005 ( 2011 ) . h. bauke , c. moore , j. b. rouquier , and d. sherrington , _ eur . b _ * 83 * , 519 ( 2011 ) . c. m. schneider , a. a. moreira , j. s. andrade jr . , s. havlin , and h. j. herrmann , _ proc . _ * 108 * , 3838 ( 2011 ) . m. faloutsos , p. faloutsos , and c. faloutsos , in ( acm , 1999 ) , p. 251 . j. onnela , j. saramaki , j. hyvonen , g. szabo , d. lazer , k. kaski , j. kertesz , and a. barabasi , _ proc . sci . _ * 104 * , 7332 ( 2007 ) . s. h. strogatz , _ nature _ * 410 * , 268 ( 2001 ) . r. v. sole , m. rosas - casals , b. corominas - murtra , and s. valverde , _ phys . e _ * 77 * , 026102 ( 2008 ) . b. monechi , v. d. servedio , and v. loreto , _ plos one _ * 10 * , e0125546 ( 2015 ) . c. ducruet , c. rozenblat , and f. zaidi , _ j. transp . geogr . _ * 18 * , 508 ( 2010 ) . e. lopez , r. parshani , r. cohen , s. carmi , and s. havlin , _ phys . _ * 99 * , 188701 ( 2007 ) . w. quattrociocchi , g. caldarelli , and a. scala , _ plos one _ * 9 * , e87986 ( 2014 ) . y. shang , _ phys . e _ * 91 * , 042804 ( 2015 ) . m. stippinger and j. kertesz , _ physica a _ * 416 * , 481 ( 2014 ) . a. majdandzic , b. podobnik , s. v. buldyrev , d. y. kenett , s. havlin , and h. e. stanley , _ nature physics _ * 10 * , 34 ( 2014 ) . a. majdandzic , l. a. braunstein , c. curme , i. vodenska , s. levy - carciente , h. e. stanley , and s. havlin , arxiv preprint arxiv:1502.00244 ( 2015 ) . j. wang , _ physica a _ * 392 * , 2257 ( 2013 ) . c. liu , d. li , e. zio , and r. kang , _ plos one _ * 9 * , e112363 ( 2014 ) . m. e. j. newman , _ networks : an introduction _ ( oxford university press , new york , 2010 ) . j. m. kleinberg , _ nature _ * 406 * , 845 ( 2000 ) . h. d. rozenfeld , c. song , and h. a. makse , _ phys . lett . _ * 104 * , 025701 ( 2010 ) . m. e. newman , _ proc . _ * 103 * , 8577 ( 2006 ) . a. clauset , m. e. j. newman , and c. moore , _ phys . * 70 * , 066111 ( 2004 ) . d. achlioptas , r. m. dsouza , and j. spencer , _ science _ * 323 * , 1453 ( 2009 ) . m. e. j. newman , _ proc . * 98 * , 404 ( 2001 ) . t. opsahl and p. panzarasa , _ soc . networks _ * 31 * , 155 ( 2009 ) .
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 usa , the self - healing algorithm re - joined almost 90% of the surviving airports .