A comparative analysis of link removal strategies in real complex weighted networks.
Journal
Scientific reports
ISSN: 2045-2322
Titre abrégé: Sci Rep
Pays: England
ID NLM: 101563288
Informations de publication
Date de publication:
03 03 2020
03 03 2020
Historique:
received:
20
09
2019
accepted:
27
01
2020
entrez:
5
3
2020
pubmed:
5
3
2020
medline:
5
3
2020
Statut:
epublish
Résumé
In this report we offer the widest comparison of links removal (attack) strategies efficacy in impairing the robustness of six real-world complex weighted networks. We test eleven different link removal strategies by computing their impact on network robustness by means of using three different measures, i.e. the largest connected cluster (LCC), the efficiency (Eff) and the total flow (TF). We find that, in most of cases, the removal strategy based on the binary betweenness centrality of the links is the most efficient to disrupt the LCC. The link removal strategies based on binary-topological network features are less efficient in decreasing the weighted measures of the network robustness (e.g. Eff and TF). Removing highest weight links first is the best strategy to decrease the efficiency (Eff) in most of the networks. Last, we found that the removal of a very small fraction of links connecting higher strength nodes or of highest weight does not affect the LCC but it determines a rapid collapse of the network efficiency Eff and the total flow TF. This last outcome raises the importance of both to adopt weighted measures of network robustness and to focus the analyses on network response to few link removals.
Identifiants
pubmed: 32127573
doi: 10.1038/s41598-020-60298-7
pii: 10.1038/s41598-020-60298-7
pmc: PMC7054356
doi:
Types de publication
Journal Article
Research Support, Non-U.S. Gov't
Langues
eng
Sous-ensembles de citation
IM
Pagination
3911Références
Albert, R., Jeong, H. & Barabasi, A. Error and attack tolerance of complex networks. Nature 406, 378–82 (2000).
pubmed: 10935628
doi: 10.1038/35019019
pmcid: 10935628
Latora, V. & Marchiori, M. Efficient Behavior of Small-World Networks. Phys. Rev. Lett. 87, 198701 (2001).
pubmed: 11690461
doi: 10.1103/PhysRevLett.87.198701
pmcid: 11690461
Pajevic, S. & Plenz, D. The organization of strong links in complex networks. Nat. Phys. 8, 429–436 (2012).
pubmed: 28890731
pmcid: 5589347
doi: 10.1038/nphys2257
Iyer, S., Killingback, T., Sundaram, B. & Wang, Z. Attack robustness and centrality of complex networks. PLoS One 8, e59613 (2013).
pubmed: 23565156
pmcid: 3615130
doi: 10.1371/journal.pone.0059613
Bellingeri, M., Cassi, D. & Vincenzi, S. Efficiency of attack strategies on complex model and real-world networks. Phys. A Stat. Mech. its Appl. 414, 174–180 (2014).
doi: 10.1016/j.physa.2014.06.079
Wandelt, S., Sun, X., Feng, D., Zanin, M. & Havlin, S. A comparative analysis of approaches to network-dismantling. Sci. Rep. 8, 1–15 (2018).
doi: 10.1038/s41598-018-31902-8
Wu, Z. & Holme, P. DiVA – Digitala Vetenskapliga Arkivet http://umu.diva-portal.org This is a pre-print version of a paper published in Physical Review E. Statistical, Nonlinear, and Soft Matter Physics. Citation for the published paper: Zhi-Xi Wu, Petter Holme Onion. (2011).
Tejedor, A., Longjas, A., Zaliapin, I., Ambroj, S. & Foufoula-Georgiou, E. Network robustness assessed within a dual connectivity framework: Joint dynamics of the Active and Idle Networks. Sci. Rep. 7, 1–10 (2017).
doi: 10.1038/s41598-017-08714-3
Caldu-Primo, J. L., Alvarez-Buylla, E. R. & Davila-Velderrain, J. Structural robustness of mammalian transcription factor networks reveals plasticity across development. Sci. Rep. 8, 1–15 (2018).
doi: 10.1038/s41598-018-32020-1
Yang, Y., Nishikawa, T. & Motter, A. E. Small vulnerable sets determine large network cascades in power grids. Science (80-.). 358, (2017).
Gallos, L. K., Cohen, R., Argyrakis, P., Bunde, A. & Havlin, S. Stability and topology of scale-free networks under attack and defense strategies. Phys. Rev. Lett. 94, 188701 (2005).
pubmed: 15904414
doi: 10.1103/PhysRevLett.94.188701
pmcid: 15904414
Chen, Y., Paul, G., Havlin, S., Liljeros, F. & Stanley, H. Finding a Better Immunization Strategy. Phys. Rev. Lett. 101, 058701 (2008).
pubmed: 18764435
doi: 10.1103/PhysRevLett.101.058701
pmcid: 18764435
Albert, R. & Barabási, A. Statistical mechanics of complex networks. Rev. Mod. Phys. 74 (2002).
Bellingeri, M. & Bodini, A. Threshold extinction in food webs. Theor. Ecol. 6, 143–152 (2013).
doi: 10.1007/s12080-012-0166-0
Bellingeri, M., Cassi, D. & Vincenzi, S. Increasing the extinction risk of highly connected species causes a sharp robust-to-fragile transition in empirical food webs. Ecol. Modell. 251, 1–8 (2013).
doi: 10.1016/j.ecolmodel.2012.12.011
Bellingeri, M., Bevacqua, D., Scotognella, F., LU, Z. M. & Cassi, D. Efficacy of local attack strategies on the Beijing road complex weighted network. Phys. A Stat. Mech. its Appl. 510, 316–328 (2018).
doi: 10.1016/j.physa.2018.06.127
Zanin, M. & Lillo, F. Modelling the air transport with complex networks: A short review. Eur. Phys. J. Spec. Top. 215, 5–21 (2013).
doi: 10.1140/epjst/e2013-01711-9
Holme, P., Kim, B. J., Yoon, C. N. & Han, S. K. Attack vulnerability of complex networks. Phys. Rev. E 65, 056109 (2002).
doi: 10.1103/PhysRevE.65.056109
Callaway, D. S., Newman, M. E., Strogatz, S. H. & Watts, D. J. Network robustness and fragility: percolation on random graphs. Phys. Rev. Lett. 85, 5468–71 (2000).
pubmed: 11136023
doi: 10.1103/PhysRevLett.85.5468
Tian, L., Bashan, A., Shi, D. N. & Liu, Y. Y. Articulation points in complex networks. Nat. Commun. 8, 1–9 (2017).
doi: 10.1038/s41467-016-0009-6
Morone, F. & Makse, H. Influence maximization in complex networks through optimal percolation. Nature 524, 65–68 (2015).
pubmed: 26131931
doi: 10.1038/nature14604
pmcid: 26131931
Da Cunha, B. R., González-Avella, J. C. & Gonçalves, S. Fast fragmentation of networks using module-based attacks. PLoS One 10, 1–15 (2015).
Granovetter, M. The Strength of Weak Ties. Am. J. Sociol. 78, 1360–1380 (1973).
doi: 10.1086/225469
Garas, A., Argyrakis, P. & Havlin, S. The structural role of weak and strong links in a financial market network. Eur. Phys. J. B 63, 265–271 (2008).
doi: 10.1140/epjb/e2008-00237-3
Onnela, J. P. et al. Analysis of a large-scale weighted network of one-to-one human communication. New J. Phys. 9, (2007).
doi: 10.1088/1367-2630/9/6/179
Onnela, J. P. et al. Structure and tie strengths in mobile communication networks. Proc. Natl. Acad. Sci. USA 104, 7332–7336 (2007).
pubmed: 17456605
doi: 10.1073/pnas.0610245104
pmcid: 17456605
Kumpula, J. M., Onnela, J. P., Saramäki, J., Kaski, K. & Kertész, J. Emergence of communities in weighted networks. Phys. Rev. Lett. 99 (2007).
Garlaschelli, D. The weighted random graph model. New J. Phys. 11, 073005 (2009).
doi: 10.1088/1367-2630/11/7/073005
Csermely, P. Weak Links. Front. Collect. 421, https://doi.org/10.1007/978-3-540-31157-7 (2009).
doi: 10.1007/978-3-540-31157-7
Bellingeri, M., Bevacqua, D., Scotognella, F. & Cassi, D. the heterogeneity in link weights may decrease the robustness of real-world complex weighted network. Sci. Rep. 1–13, https://doi.org/10.1038/s41598-019-47119-2 (2019).
Bellingeri, M., Agliari, E. & Cassi, D. Optimization strategies with resource scarcity: from immunization of networks to the traveling salesman problem. Mod. Phys. Lett. B (2015).
Schneider, C. M., Mihaljev, T. & Herrmann, H. J. Inverse targeting —An effective immunization strategy. EPL (Europhysics Lett. 98, 46002 (2012).
doi: 10.1209/0295-5075/98/46002
Bullmore, E. & Sporns, O. The economy of brain network organization. Nat. Rev. Neurosci. 13, 336–349 (2012).
pubmed: 22498897
doi: 10.1038/nrn3214
pmcid: 22498897
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M. & Hwang, D. Complex networks: Structure and dynamics. Phys. Rep. 424, 175–308 (2006).
doi: 10.1016/j.physrep.2005.10.009
Bellingeri, M. & Cassi, D. Robustness of weighted networks. Phys. A Stat. Mech. its Appl. 489, 47–55 (2018).
doi: 10.1016/j.physa.2017.07.020
Freeman, H. E. A Set of Measures of Centrality Based on Betweenness. Sociometry 40 (1977).
doi: 10.2307/3033543
Barrat, A., Barthélemy, M., Pastor-Satorras, R. & Vespignani, A. The architecture of complex weighted networks. Proc. Natl. Acad. Sci. USA 101, 3747–3752 (2004).
pubmed: 15007165
doi: 10.1073/pnas.0400087101
pmcid: 15007165
Colizza, V., Pastor-Satorras, R. & Vespignani, A. Reaction-diffusion processes and metapopulation models in heterogeneous networks. Nat. Phys. 3, 276–282 (2007).
doi: 10.1038/nphys560
Watts, D. J. & Strogatz, S. H. Collective dynamics of ‘small-world’ networks. Nature 393, 440–2 (1998).
pubmed: 9623998
doi: 10.1038/30918
pmcid: 9623998
Newman, M. E. J. Analysis of weighted networks. Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys. 70, 1–9 (2004).
Kaluza, P., Kölzsch, A., Gastner, M. T. & Blasius, B. The complex network of global cargo ship movements. J. R. Soc. Interface 7, 1093–1103 (2010).
pubmed: 20086053
pmcid: 2880080
doi: 10.1098/rsif.2009.0495
Serrano, M. Á., Boguñá, M. & Sagués, F. Uncovering the hidden geometry behind metabolic networks. Mol. Biosyst. 8, 843–850 (2012).
pubmed: 22228307
doi: 10.1039/c2mb05306c
pmcid: 22228307
Nepusz, T., Petróczi, A., Négyessy, L. & Bazsó, F. Fuzzy communities and the concept of bridgeness in complex networks. Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys. 77, 1–12 (2008).
doi: 10.1103/PhysRevE.77.016107
Dall’Asta, L., Barrat, A., Barthélemy, M. & Vespignani, A. Vulnerability of weighted networks. J. Stat. Mech. Theory Exp. 04006, (2006).
Schneider, C. M., Moreira, A. A., Andrade, S., Havlin, S. & Herrmann, H. J. Onion-like network topology enhances robustness. J. Stat. Mech. Theory Exp. 1–4 (2011).
Nguyen, Q., Pham, H. D., Cassi, D. & Bellingeri, M. Conditional attack strategy for real-world complex networks. Phys. A Stat. Mech. its Appl. 530, 121561 (2019).
doi: 10.1016/j.physa.2019.121561
Latora, V. & Marchiori, M. Economic small-world behavior in weighted networks. Eur. Phys. J. B 32, 249–263 (2003).
doi: 10.1140/epjb/e2003-00095-5
Pan, R. K. & Saramäki, J. The strength of strong ties in scientific collaboration networks. Epl. 97 (2012).
Barra, A. & Agliari, E. A statistical mechanics approach to Granovetter theory. Phys. A Stat. Mech. its Appl. 391, 3017–3026 (2012).
doi: 10.1016/j.physa.2012.01.007
Agliari, E., Cioli, C. & Guadagnini, E. Percolation on correlated random networks. Phys. Rev. E 84, 031120 (2011).
doi: 10.1103/PhysRevE.84.031120