Simple and efficient self-healing strategy for damaged complex networks

Lazaros Gallos, Nina H. Fefferman

Research output: Contribution to journalArticle

14 Citations (Scopus)

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 the USA, the self-healing algorithm rejoined almost 90% of the surviving airports.

Original languageEnglish (US)
Article number052806
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Volume92
Issue number5
DOIs
StatePublished - Nov 10 2015

Fingerprint

healing
Complex Networks
Vertex of a graph
airports
Damage
damage
Reverse
leaves
Cycle
Strategy
cycles
Demonstrate
Model

All Science Journal Classification (ASJC) codes

  • Condensed Matter Physics
  • Statistical and Nonlinear Physics
  • Statistics and Probability

Cite this

@article{f1bbd921899e450ca19466517290c372,
title = "Simple and efficient self-healing strategy for damaged complex networks",
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 the USA, the self-healing algorithm rejoined almost 90{\%} of the surviving airports.",
author = "Lazaros Gallos and Fefferman, {Nina H.}",
year = "2015",
month = "11",
day = "10",
doi = "https://doi.org/10.1103/PhysRevE.92.052806",
language = "English (US)",
volume = "92",
journal = "Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics",
issn = "1063-651X",
publisher = "American Physical Society",
number = "5",

}

Simple and efficient self-healing strategy for damaged complex networks. / Gallos, Lazaros; Fefferman, Nina H.

In: Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, Vol. 92, No. 5, 052806, 10.11.2015.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Simple and efficient self-healing strategy for damaged complex networks

AU - Gallos, Lazaros

AU - Fefferman, Nina H.

PY - 2015/11/10

Y1 - 2015/11/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84947246679&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947246679&partnerID=8YFLogxK

U2 - https://doi.org/10.1103/PhysRevE.92.052806

DO - https://doi.org/10.1103/PhysRevE.92.052806

M3 - Article

VL - 92

JO - Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics

JF - Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics

SN - 1063-651X

IS - 5

M1 - 052806

ER -