IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v428y2015icp368-382.html
   My bibliography  Save this article

Network robustness and random processes

Author

Listed:
  • Vodák, Rostislav
  • Bíl, Michal
  • Sedoník, Jiří

Abstract

We introduce two new measures of network robustness and apply them to four different strategies. The measures are independent from the number of nodes in the network and have the strong potential to cover a large portfolio of applications. Using the Monte-Carlo methods, we demonstrate how to approximate the measures. The methods are based on random interruption of links with suitable constraints which represent the above-mentioned strategies. We introduce two networks with obvious varying robustness to demonstrate the measures. We also demonstrate how to employ the measures in order to improve the robustness of the networks by adding one new link. We further indicate that the measures are able to identify the infrequently connected parts of the network and suggest the most appropriate improvement. We also discuss the consequences of the obtained results and the possible applications of the measures.

Suggested Citation

  • Vodák, Rostislav & Bíl, Michal & Sedoník, Jiří, 2015. "Network robustness and random processes," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 428(C), pages 368-382.
    • Handle: RePEc:eee:phsmap:v:428:y:2015:i:c:p:368-382
    DOI: 10.1016/j.physa.2015.01.056
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437115000758
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2015.01.056?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Morohosi, Hozumi, 2010. "Measuring the network robustness by Monte Carlo estimation of shortest path length distribution," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 81(3), pages 551-559.
    2. Beygelzimer, Alina & Grinstein, Geoffrey & Linsker, Ralph & Rish, Irina, 2005. "Improving network robustness by edge modification," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 357(3), pages 593-612.
    3. Mishkovski, Igor & Righero, Marco & Biey, Mario & Kocarev, Ljupco, 2011. "Enhancing robustness and synchronizability of networks homogenizing their degree distribution," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(23), pages 4610-4620.
    4. Cao, Xian-Bin & Hong, Chen & Du, Wen-Bo & Zhang, Jun, 2013. "Improving the network robustness against cascading failures by adding links," Chaos, Solitons & Fractals, Elsevier, vol. 57(C), pages 35-40.
    5. 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.
    6. Santiago, A. & Benito, R.M., 2009. "Robustness of heterogeneous complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(11), pages 2234-2242.
    7. Pu, Cun-Lai & Yang, Jian & Pei, Wen-Jiang & Tao, Yu-Ting & Lan, Shao-Hua, 2013. "Robustness analysis of static routing on networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(15), pages 3293-3300.
    8. Frank Emmert-Streib & Matthias Dehmer, 2008. "Robustness In Scale-Free Networks: Comparing Directed And Undirected Networks," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 19(05), pages 717-726.
    9. Paul, Gerald & Sreenivasan, Sameet & Havlin, Shlomo & Eugene Stanley, H., 2006. "Optimization of network robustness to random breakdowns," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 370(2), pages 854-862.
    10. E. Estrada, 2006. "Network robustness to targeted attacks. The interplay of expansibility and degree distribution," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 52(4), pages 563-574, August.
    11. G. Paul & T. Tanizawa & S. Havlin & H. Stanley, 2004. "Optimization of robustness of complex networks," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 38(2), pages 187-191, March.
    12. 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.
    13. Snelder, M. & van Zuylen, H.J. & Immers, L.H., 2012. "A framework for robustness analysis of road networks for short term variations in supply," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(5), pages 828-842.
    Full references (including those not matched with items on IDEAS)

    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. Dong, Gaogao & Tian, Lixin & Du, Ruijin & Fu, Min & Stanley, H. Eugene, 2014. "Analysis of percolation behaviors of clustered networks with partial support–dependence relations," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 394(C), pages 370-378.
    2. Wen, Xiangxi & Tu, Congliang & Wu, Minggong, 2018. "Node importance evaluation in aviation network based on “No Return” node deletion method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 503(C), pages 546-559.
    3. Cui, Pengshuai & Zhu, Peidong & Wang, Ke & Xun, Peng & Xia, Zhuoqun, 2018. "Enhancing robustness of interdependent network by adding connectivity and dependence links," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 497(C), pages 185-197.
    4. Ji, Xingpei & Wang, Bo & Liu, Dichen & Chen, Guo & Tang, Fei & Wei, Daqian & Tu, Lian, 2016. "Improving interdependent networks robustness by adding connectivity links," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 444(C), pages 9-19.
    5. Xia Cao & Chuanyun Li & Wei Chen & Jinqiu Li & Chaoran Lin, 2020. "Research on the invulnerability and optimization of the technical cooperation innovation network based on the patent perspective—A case study of new energy vehicles," PLOS ONE, Public Library of Science, vol. 15(9), pages 1-19, September.
    6. Das, Sai Saranga & Raman, Karthik, 2022. "Effect of dormant spare capacity on the attack tolerance of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 598(C).
    7. Yu, Yang & Deng, Ye & Tan, Suo-Yi & Wu, Jun, 2018. "Efficient disintegration strategy in directed networks based on tabu search," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 507(C), pages 435-442.
    8. Peng, Guan-sheng & Wu, Jun, 2016. "Optimal network topology for structural robustness based on natural connectivity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 443(C), pages 212-220.
    9. Aybike Ulusan & Ozlem Ergun, 2018. "Restoration of services in disrupted infrastructure systems: A network science approach," PLOS ONE, Public Library of Science, vol. 13(2), pages 1-28, February.
    10. Zhu, Qian & Zhu, Zhiliang & Wang, Yifan & Yu, Hai, 2016. "Fuzzy-information-based robustness of interconnected networks against attacks and failures," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 458(C), pages 194-203.
    11. Heng Ye & Zhiping Li & Guangyue Li & Yiran Liu, 2022. "Topology Analysis of Natural Gas Pipeline Networks Based on Complex Network Theory," Energies, MDPI, vol. 15(11), pages 1-20, May.
    12. Hu, Xinlei & Huang, Jie & Shi, Feng, 2022. "A robustness assessment with passenger flow data of high-speed rail network in China," Chaos, Solitons & Fractals, Elsevier, vol. 165(P1).
    13. Tomassini, Marco, 2023. "Designing robust scale-free networks under targeted link attack using local information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 615(C).
    14. Jiang, Zhong-Yuan & Zeng, Yong & Liu, Zhi-Hong & Ma, Jian-Feng, 2019. "Identifying critical nodes’ group in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 121-132.
    15. 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.
    16. Ou, Ruiqiu & Yang, Jianmei, 2012. "On structural properties of scale-free networks with finite size," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(3), pages 887-894.
    17. Xu, Mengqiao & Deng, Wenhui & Zhu, Yifan & LÜ, Linyuan, 2023. "Assessing and improving the structural robustness of global liner shipping system: A motif-based network science approach," Reliability Engineering and System Safety, Elsevier, vol. 240(C).
    18. Kazawa, Yui & Tsugawa, Sho, 2020. "Effectiveness of link-addition strategies for improving the robustness of both multiplex and interdependent networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    19. Kyu-Min Lee & Jae-Suk Yang & Gunn Kim & Jaesung Lee & Kwang-Il Goh & In-mook Kim, 2010. "Impact of the topology of global macroeconomic network on the spreading of economic crises," Papers 1011.4336, arXiv.org, revised Apr 2011.
    20. Milena Oehlers & Benjamin Fabian, 2021. "Graph Metrics for Network Robustness—A Survey," Mathematics, MDPI, vol. 9(8), pages 1-48, April.

    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:eee:phsmap:v:428:y:2015:i:c:p:368-382. 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: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    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.