  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.
