Evaluation of network robustness using a node tearing algorithm
AbstractUntil recently the study of failure and vulnerability in complex networks focused on the role of high degree nodes, and the relationship between their removal and network connectivity. Recent evidence suggested that in some network configurations, the removal of lower degree nodes can also cause network fragmentation. We present a disassembling algorithm that identifies nodes that are core to network connectivity. The algorithm is based on network tearing in which communities are defined and used to construct a hierarchical structure. Cut-nodes, which are located at the boundaries of the communities, are the key interest. Their importance in the overall network connectivity is characterized by their participation with neighbouring communities in each level of the hierarchy. We examine the impact of these cut-nodes by studying the change in size of the giant component, local and global efficiencies, and how the algorithm can be combined with other community detection methods to reveal the finer internal structure within a community.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Bibliographic InfoArticle provided by Elsevier in its journal Physica A: Statistical Mechanics and its Applications.
Volume (Year): 391 (2012)
Issue (Month): 24 ()
Contact details of provider:
Web page: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/
Network tearing; Network connectivity; Vulnerability in complex networks; Community;
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Sun, Shiwen & Liu, Zhongxin & Chen, Zengqiang & Yuan, Zhuzhi, 2007. "Error and attack tolerance of evolving networks with local preferential attachment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 373(C), pages 851-860.
- Ghedini, Cinara G. & Ribeiro, Carlos H.C., 2011. "Rethinking failure and attack tolerance assessment in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(23), pages 4684-4691.
- Colizza, Vittoria & Flammini, Alessandro & Maritan, Amos & Vespignani, Alessandro, 2005. "Characterization and modeling of protein–protein interaction networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 352(1), pages 1-27.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Wendy Shamier).
If references are entirely missing, you can add them using this form.