IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i8p895-d538084.html
   My bibliography  Save this article

Graph Metrics for Network Robustness—A Survey

Author

Listed:
  • Milena Oehlers

    (Department of Physics, Technische Universität Berlin, 10623 Berlin, Germany
    Information Systems, Humboldt-Universität zu Berlin, 10178 Berlin, Germany)

  • Benjamin Fabian

    (Information Systems, Humboldt-Universität zu Berlin, 10178 Berlin, Germany
    E-Government, Technical University of Applied Sciences Wildau, 15745 Wildau, Germany)

Abstract

Research on the robustness of networks, and in particular the Internet, has gained critical importance in recent decades because more and more individuals, societies and firms rely on this global network infrastructure for communication, knowledge transfer, business processes and e-commerce. In particular, modeling the structure of the Internet has inspired several novel graph metrics for assessing important topological robustness features of large complex networks. This survey provides a comparative overview of these metrics, presents their strengths and limitations for analyzing the robustness of the Internet topology, and outlines a conceptual tool set in order to facilitate their future adoption by Internet research and practice but also other areas of network science.

Suggested Citation

  • Milena Oehlers & Benjamin Fabian, 2021. "Graph Metrics for Network Robustness—A Survey," Mathematics, MDPI, vol. 9(8), pages 1-48, April.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:8:p:895-:d:538084
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/8/895/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/8/895/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Trpevski, Daniel & Smilkov, Daniel & Mishkovski, Igor & Kocarev, Ljupco, 2010. "Vulnerability of labeled networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(23), pages 5538-5549.
    2. Szabó, Gábor J. & Alava, Mikko & Kertész, János, 2003. "Geometry of minimum spanning trees on scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 330(1), pages 31-36.
    3. Réka Albert & Hawoong Jeong & Albert-László Barabási, 2000. "Error and attack tolerance of complex networks," Nature, Nature, vol. 406(6794), pages 378-382, July.
    4. 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.
    5. Duncan J. Watts & Steven H. Strogatz, 1998. "Collective dynamics of ‘small-world’ networks," Nature, Nature, vol. 393(6684), pages 440-442, June.
    6. Wang, Bing & Tang, Huanwen & Guo, Chonghui & Xiu, Zhilong, 2006. "Entropy optimization of scale-free networks’ robustness to random failures," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 363(2), pages 591-596.
    7. 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.
    8. Roger Guimerà & Luís A. Nunes Amaral, 2005. "Functional cartography of complex metabolic networks," Nature, Nature, vol. 433(7028), pages 895-900, February.
    9. Matthias Lischke & Benjamin Fabian, 2016. "Analyzing the Bitcoin Network: The First Four Years," Future Internet, MDPI, vol. 8(1), pages 1-40, March.
    10. Steven H. Strogatz, 2001. "Exploring complex networks," Nature, Nature, vol. 410(6825), pages 268-276, March.
    11. Barthélemy, Marc & Barrat, Alain & Pastor-Satorras, Romualdo & Vespignani, Alessandro, 2005. "Characterization and modeling of weighted networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 346(1), pages 34-43.
    12. Crucitti, Paolo & Latora, Vito & Marchiori, Massimo & Rapisarda, Andrea, 2003. "Efficiency of scale-free networks: error and attack tolerance," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 320(C), pages 622-642.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Roger Arnau & José M. Calabuig & Luis M. García-Raffi & Enrique A. Sánchez Pérez & Sergi Sanjuan, 2024. "A Bellman–Ford Algorithm for the Path-Length-Weighted Distance in Graphs," Mathematics, MDPI, vol. 12(16), pages 1-16, August.
    2. David G. Green, 2023. "Emergence in complex networks of simple agents," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 18(3), pages 419-462, July.
    3. Zhang, Yin-Ting & Zhou, Wei-Xing, 2023. "Quantifying the status of economies in international crop trade networks: A correlation structure analysis of various node-ranking metrics," Chaos, Solitons & Fractals, Elsevier, vol. 172(C).
    4. Franken, Jonas & Reinhold, Thomas & Reichert, Lilian & Reuter, Christian, 2022. "The digital divide in state vulnerability to submarine communications cable failure," International Journal of Critical Infrastructure Protection, Elsevier, vol. 38(C).
    5. Nie, Tingyuan & Fan, Bo & Wang, Zhenhao, 2022. "Complexity and robustness of weighted circuit network of placement," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 598(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jalili, Mahdi, 2011. "Error and attack tolerance of small-worldness in complex networks," Journal of Informetrics, Elsevier, vol. 5(3), pages 422-430.
    2. Viljoen, Nadia M. & Joubert, Johan W., 2016. "The vulnerability of the global container shipping network to targeted link disruption," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 462(C), pages 396-409.
    3. Jing Liu & Huapu Lu & He Ma & Wenzhi Liu, 2017. "Network Vulnerability Analysis of Rail Transit Plans in Beijng-Tianjin-Hebei Region Considering Connectivity Reliability," Sustainability, MDPI, vol. 9(8), pages 1-17, August.
    4. Jalili, Mahdi, 2011. "Synchronizability of dynamical scale-free networks subject to random errors," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(23), pages 4588-4595.
    5. Nie, Tingyuan & Fan, Bo & Wang, Zhenhao, 2022. "Complexity and robustness of weighted circuit network of placement," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 598(C).
    6. Kashyap, G. & Ambika, G., 2019. "Link deletion in directed complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 631-643.
    7. Kashin Sugishita & Yasuo Asakura, 2021. "Vulnerability studies in the fields of transportation and complex networks: a citation network analysis," Public Transport, Springer, vol. 13(1), pages 1-34, March.
    8. Zhang, Jianhua & Wang, Shuliang & Wang, Xiaoyuan, 2018. "Comparison analysis on vulnerability of metro networks based on complex network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 72-78.
    9. Hao, Yucheng & Jia, Limin & Wang, Yanhui, 2020. "Edge attack strategies in interdependent scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 540(C).
    10. Saniee Monfared, Momhammad Ali & Jalili, Mahdi & Alipour, Zohreh, 2014. "Topology and vulnerability of the Iranian power grid," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 406(C), pages 24-33.
    11. Ma, A. & Mondragón, R.J., 2012. "Evaluation of network robustness using a node tearing algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(24), pages 6674-6681.
    12. Kong, Linghao & Wang, Lizhi & Cao, Zhongzheng & Wang, Xiaohong, 2024. "Resilience evaluation of UAV swarm considering resource supplementation," Reliability Engineering and System Safety, Elsevier, vol. 241(C).
    13. Lv, Changchun & Yuan, Ziwei & Si, Shubin & Duan, Dongli & Yao, Shirui, 2022. "Cascading failure in networks with dynamical behavior against multi-node removal," Chaos, Solitons & Fractals, Elsevier, vol. 160(C).
    14. Vinayak, & Raghuvanshi, Adarsh & kshitij, Avinash, 2023. "Signatures of capacity development through research collaborations in artificial intelligence and machine learning," Journal of Informetrics, Elsevier, vol. 17(1).
    15. Yang, Hyeonchae & Jung, Woo-Sung, 2016. "Structural efficiency to manipulate public research institution networks," Technological Forecasting and Social Change, Elsevier, vol. 110(C), pages 21-32.
    16. Yao, Jialing & Sun, Bingbin & Xi, lifeng, 2019. "Fractality of evolving self-similar networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 515(C), pages 211-216.
    17. Zhou, Yaoming & Wang, Junwei, 2018. "Efficiency of complex networks under failures and attacks: A percolation approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 658-664.
    18. Leto Peel & Tiago P. Peixoto & Manlio De Domenico, 2022. "Statistical inference links data and theory in network science," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    19. Biao Xiong & Bixin Li & Rong Fan & Qingzhong Zhou & Wu Li, 2017. "Modeling and Simulation for Effectiveness Evaluation of Dynamic Discrete Military Supply Chain Networks," Complexity, Hindawi, vol. 2017, pages 1-9, October.
    20. Zhao, Jianyu & Wei, Jiang & Yu, Lean & Xi, Xi, 2022. "Robustness of knowledge networks under targeted attacks: Electric vehicle field of China evidence," Structural Change and Economic Dynamics, Elsevier, vol. 63(C), pages 367-382.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:9:y:2021:i:8:p:895-:d:538084. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.