Simple and efficient self-healing strategy for damaged complex networks
arXiv:1511.06729 · doi:10.1103/PhysRevE.92.052806
Abstract
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.
arXiv comment10 pages, 8 figures
References in corpus (19)
- Modularity and community structure in networks
- Finding community structure in very large networks
- Error and attack tolerance of complex networks
- The structure of scientific collaboration networks
- Network robustness and fragility: Percolation on random graphs
- Resilience of the Internet to random breakdowns
- Structure and tie strengths in mobile communication networks
- Breakdown of the Internet under intentional attack
- Mitigation of Malicious Attacks on Networks
- Robustness of the European power grids under intentional attack
- Exact solutions for models of evolving networks with addition and deletion of nodes
- Small world-Fractal Transition in Complex Networks: Renormalization Group Approach
- How to make a fragile network robust and vice versa
- Self-healing networks: redundancy and structure
- Enhancing resilience of interdependent networks by healing
- Limited path percolation in complex networks
- Evolving networks through deletion and duplication
- Topological phase transition in a network model with preferential attachment and node removal
- Scale free networks by preferential depletion
Cited by in corpus (8)
- Network resilience
- Asymmetry in interdependence makes a multilayer system more robust against cascading failures
- A new design principle of robust onion-like networks self-organized in growth
- Improving the Survivability of Clustered Interdependent Networks by Restructuring Dependencies
- A Decentralised Self-Healing Approach for Network Topology Maintenance
- More Tolerant Reconstructed Networks by Self-Healing against Attacks in Saving Resource
- Effective Self-Healing Networks against Attacks or Disasters in Resource Allocation Control
- DeepPR: Progressive Recovery for Interdependent VNFs with Deep Reinforcement Learning