IDEAS home Printed from https://ideas.repec.org/a/eee/reensy/v183y2019icp276-280.html
   My bibliography  Save this article

Exact calculation of network robustness

Author

Listed:
  • Lordan, Oriol
  • Albareda-Sambola, Maria

Abstract

Finding the most critical nodes regarding network connectivity has attracted the attention of many researchers in infrastructure networks, power grids, transportation networks and physics in complex networks. Static robustness of networks under intentional attacks analyses the ability of a system to maintain its connectivity after the disconnection or deletion of a series of targeted nodes. In this context, connectivity is typically measured by the size of the remaining largest connected component. When targeting these nodes, previous literature has mostly used adaptive strategies that sequentially remove central nodes, or created heuristics in order to improve the results of the adaptive strategies. The proposed methodology based on mathematical programming allows to identify, for every fraction of disconnected or removed nodes, the set that minimizes the size of the largest connected component of a network, i.e. it allows to calculate the exact (most critical) robustness of a network.

Suggested Citation

  • Lordan, Oriol & Albareda-Sambola, Maria, 2019. "Exact calculation of network robustness," Reliability Engineering and System Safety, Elsevier, vol. 183(C), pages 276-280.
    • Handle: RePEc:eee:reensy:v:183:y:2019:i:c:p:276-280
    DOI: 10.1016/j.ress.2018.11.020
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0951832018307671
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ress.2018.11.020?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. Lordan, Oriol & Sallan, Jose M. & Escorihuela, Nuria & Gonzalez-Prieto, David, 2016. "Robustness of airline route networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 445(C), pages 18-26.
    2. Deng, Ye & Wu, Jun & Tan, Yue-jin, 2016. "Optimal attack strategy of complex networks based on tabu search," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 442(C), pages 74-81.
    3. Marco Di Summa & Andrea Grosso & Marco Locatelli, 2012. "Branch and cut algorithms for detecting critical nodes in undirected graphs," Computational Optimization and Applications, Springer, vol. 53(3), pages 649-680, December.
    4. Fenling Feng & Lei Wang, 2013. "Robustness Measure of China’s Railway Network Topology Using Relative Entropy," Discrete Dynamics in Nature and Society, Hindawi, vol. 2013, pages 1-8, October.
    5. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2014. "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 233-273, July.
    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. Meng, Xueyu & Cai, Zhiqiang & Si, Shubin & Duan, Dongli, 2021. "Analysis of epidemic vaccination strategies on heterogeneous networks: Based on SEIRV model and evolutionary game," Applied Mathematics and Computation, Elsevier, vol. 403(C).
    2. Wang, Ning & Gao, Ying & He, Jia-tao & Yang, Jun, 2022. "Robustness evaluation of the air cargo network considering node importance and attack cost," Reliability Engineering and System Safety, Elsevier, vol. 217(C).
    3. Dui, Hongyan & Meng, Xueyu & Xiao, Hui & Guo, Jianjun, 2020. "Analysis of the cascading failure for scale-free networks based on a multi-strategy evolutionary game," Reliability Engineering and System Safety, Elsevier, vol. 199(C).
    4. Li, Tao & Rong, Lili, 2020. "A comprehensive method for the robustness assessment of high-speed rail network with operation data: A case in China," Transportation Research Part A: Policy and Practice, Elsevier, vol. 132(C), pages 666-681.
    5. Zhao, Jianyu & Yu, Lean & Xi, Xi & Li, Shengliang, 2023. "Knowledge percolation threshold and optimization strategies of the combinatorial network for complex innovation in the digital economy," Omega, Elsevier, vol. 120(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. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    2. Marco Di Summa & Syed Md Omar Faruk, 2023. "Critical node/edge detection problems on trees," 4OR, Springer, vol. 21(3), pages 439-455, September.
    3. Bernardetta Addis & Roberto Aringhieri & Andrea Grosso & Pierre Hosteins, 2016. "Hybrid constructive heuristics for the critical node problem," Annals of Operations Research, Springer, vol. 238(1), pages 637-649, March.
    4. Chen, Wei & Jiang, Manrui & Jiang, Cheng & Zhang, Jun, 2020. "Critical node detection problem for complex network in undirected weighted networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 538(C).
    5. Wei, Ningji & Walteros, Jose L., 2022. "Integer programming methods for solving binary interdiction games," European Journal of Operational Research, Elsevier, vol. 302(2), pages 456-469.
    6. Zhong, Haonan & Mahdavi Pajouh, Foad & A． Prokopyev, Oleg, 2023. "On designing networks resilient to clique blockers," European Journal of Operational Research, Elsevier, vol. 307(1), pages 20-32.
    7. Zhou, Yangming & Wang, Gezi & Hao, Jin-Kao & Geng, Na & Jiang, Zhibin, 2023. "A fast tri-individual memetic search approach for the distance-based critical node problem," European Journal of Operational Research, Elsevier, vol. 308(2), pages 540-554.
    8. Mahdavi Pajouh, Foad & Walteros, Jose L. & Boginski, Vladimir & Pasiliao, Eduardo L., 2015. "Minimum edge blocker dominating set problem," European Journal of Operational Research, Elsevier, vol. 247(1), pages 16-26.
    9. Bernardetta Addis & Roberto Aringhieri & Andrea Grosso & Pierre Hosteins, 2016. "Hybrid constructive heuristics for the critical node problem," Annals of Operations Research, Springer, vol. 238(1), pages 637-649, March.
    10. Alexander Veremyev & Konstantin Pavlikov & Eduardo L. Pasiliao & My T. Thai & Vladimir Boginski, 2019. "Critical nodes in interdependent networks with deterministic and probabilistic cascading failures," Journal of Global Optimization, Springer, vol. 74(4), pages 803-838, August.
    11. Ningji Wei & Jose L. Walteros & Foad Mahdavi Pajouh, 2021. "Integer Programming Formulations for Minimum Spanning Tree Interdiction," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1461-1480, October.
    12. Hooshmand, F. & Mirarabrazi, F. & MirHassani, S.A., 2020. "Efficient Benders decomposition for distance-based critical node detection problem," Omega, Elsevier, vol. 93(C).
    13. Ventresca, Mario & Harrison, Kyle Robert & Ombuki-Berman, Beatrice M., 2018. "The bi-objective critical node detection problem," European Journal of Operational Research, Elsevier, vol. 265(3), pages 895-908.
    14. Hosseinali Salemi & Austin Buchanan, 2022. "Solving the Distance-Based Critical Node Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1309-1326, May.
    15. Laure Rousset & César Ducruet, 2020. "Disruptions in Spatial Networks: a Comparative Study of Major Shocks Affecting Ports and Shipping Patterns," Networks and Spatial Economics, Springer, vol. 20(2), pages 423-447, June.
    16. Zhou, Yaoming & Wang, Junwei & Huang, George Q., 2019. "Efficiency and robustness of weighted air transport networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 14-26.
    17. Lordan, Oriol & Sallan, Jose M., 2019. "Core and critical cities of global region airport networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 513(C), pages 724-733.
    18. Gokhan Karakose & Ronald G. McGarvey, 2019. "Optimal Detection of Critical Nodes: Improvements to Model Structure and Performance," Networks and Spatial Economics, Springer, vol. 19(1), pages 1-26, March.
    19. Yajun Xiong & Hui Tang & Xiaobo Tian, 2022. "Research on Structural Toughness of Railway City Network in Yellow River Basin and Case Study of Zhengzhou 7–20 Rainstorm Disaster," Sustainability, MDPI, vol. 14(19), pages 1-17, September.
    20. 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.

    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:reensy:v:183:y:2019:i:c:p:276-280. 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: https://www.journals.elsevier.com/reliability-engineering-and-system-safety .

    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.