IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v74y2019i4d10.1007_s10898-018-0703-5.html
   My bibliography  Save this article

Critical nodes in interdependent networks with deterministic and probabilistic cascading failures

Author

Listed:
  • Alexander Veremyev

    (University of Central Florida)

  • Konstantin Pavlikov

    (University of Southern Denmark)

  • Eduardo L. Pasiliao

    (Air Force Research Laboratory)

  • My T. Thai

    (University of Florida)

  • Vladimir Boginski

    (University of Central Florida)

Abstract

We consider optimization problems of identifying critical nodes in coupled interdependent networks, that is, choosing a subset of nodes whose deletion causes the maximum network fragmentation (quantified by an appropriate metric) in the presence of deterministic or probabilistic cascading failure propagations. We use two commonly considered network fragmentation metrics: total number of disabled nodes and total number of disabled pair-wise connectivities. First, we discuss computational complexity issues and develop linear mixed integer programming (MIP) formulations for the corresponding optimization problems in the deterministic case. We then extend these problems to the case with probabilistic failure propagations using Conditional Value-at-Risk measure. We develop a scenario-based linear MIP model and propose an exact Markov chain-based algorithm to solve these problems. Finally, we perform a series of computational experiments on synthetic and semi-synthetic networks and discuss some interesting insights that illustrate the properties of the proposed models.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jglopt:v:74:y:2019:i:4:d:10.1007_s10898-018-0703-5
    DOI: 10.1007/s10898-018-0703-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-018-0703-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-018-0703-5?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. Veremyev, Alexander & Sorokin, Alexey & Boginski, Vladimir & Pasiliao, Eduardo L., 2014. "Minimum vertex cover problem for coupled interdependent networks with cascading failures," European Journal of Operational Research, Elsevier, vol. 232(3), pages 499-511.
    2. Ouyang, Min, 2014. "Review on modeling and simulation of interdependent critical infrastructure systems," Reliability Engineering and System Safety, Elsevier, vol. 121(C), pages 43-60.
    3. 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.
    4. Sergey V. Buldyrev & Roni Parshani & Gerald Paul & H. Eugene Stanley & Shlomo Havlin, 2010. "Catastrophic cascade of failures in interdependent networks," Nature, Nature, vol. 464(7291), pages 1025-1028, April.
    5. Johansson, Jonas & Hassel, Henrik, 2010. "An approach for modelling interdependent infrastructures in the context of vulnerability analysis," Reliability Engineering and System Safety, Elsevier, vol. 95(12), pages 1335-1344.
    6. Drossel, B. & Schwabl, F., 1993. "Forest-fire model with immune trees," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 199(2), pages 183-197.
    7. Wang, Shuliang & Hong, Liu & Chen, Xueguang, 2012. "Vulnerability analysis of interdependent infrastructure systems: A methodological framework," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(11), pages 3323-3335.
    8. Maarten Oosten & Jeroen H. G. C. Rutten & Frits C. R. Spieksma, 2007. "Disconnecting graphs by removing vertices: a polyhedral approach," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 61(1), pages 35-60, February.
    9. Rockafellar, R. Tyrrell & Uryasev, Stanislav, 2002. "Conditional value-at-risk for general loss distributions," Journal of Banking & Finance, Elsevier, vol. 26(7), pages 1443-1471, July.
    10. 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.
    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. Alla Kammerdiner & Alexander Semenov & Eduardo L. Pasiliao, 2023. "Flight from COVID-19: Multiscale and Multilayer Analyses of the Epidemic-Induced Network Adaptations," SN Operations Research Forum, Springer, vol. 4(2), pages 1-22, June.

    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. Zhao, Chen & Li, Nan & Fang, Dongping, 2018. "Criticality assessment of urban interdependent lifeline systems using a biased PageRank algorithm and a multilayer weighted directed network model," International Journal of Critical Infrastructure Protection, Elsevier, vol. 22(C), pages 100-112.
    2. Hausken, Kjell, 2024. "Fifty Years of Operations Research in Defense," European Journal of Operational Research, Elsevier, vol. 318(2), pages 355-368.
    3. Brunner, L.G. & Peer, R.A.M. & Zorn, C. & Paulik, R. & Logan, T.M., 2024. "Understanding cascading risks through real-world interdependent urban infrastructure," Reliability Engineering and System Safety, Elsevier, vol. 241(C).
    4. Wu, Baichao & Tang, Aiping & Wu, Jie, 2016. "Modeling cascading failures in interdependent infrastructures under terrorist attacks," Reliability Engineering and System Safety, Elsevier, vol. 147(C), pages 1-8.
    5. Gao, Xingle & Peng, Minfang & Tse, Chi K., 2022. "Robustness analysis of cyber-coupled power systems with considerations of interdependence of structures, operations and dynamic behaviors," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 596(C).
    6. 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).
    7. Almoghathawi, Yasser & Barker, Kash & Albert, Laura A., 2019. "Resilience-driven restoration model for interdependent infrastructure networks," Reliability Engineering and System Safety, Elsevier, vol. 185(C), pages 12-23.
    8. Wang, Weiping & Yang, Saini & Hu, Fuyu & Stanley, H. Eugene & He, Shuai & Shi, Mimi, 2018. "An approach for cascading effects within critical infrastructure systems," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 510(C), pages 164-177.
    9. Hassan Al-Zarooni & Hamdi Bashir, 2020. "An integrated ISM fuzzy MICMAC approach for modeling and analyzing electrical power system network interdependencies," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 11(6), pages 1204-1226, December.
    10. Ouyang, Min & Pan, ZheZhe & Hong, Liu & He, Yue, 2015. "Vulnerability analysis of complementary transportation systems with applications to railway and airline systems in China," Reliability Engineering and System Safety, Elsevier, vol. 142(C), pages 248-257.
    11. Kim, Dong Hwan & Eisenberg, Daniel A. & Chun, Yeong Han & Park, Jeryang, 2017. "Network topology and resilience analysis of South Korean power grid," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 465(C), pages 13-24.
    12. Liu, Wei & Song, Zhaoyang, 2020. "Review of studies on the resilience of urban critical infrastructure networks," Reliability Engineering and System Safety, Elsevier, vol. 193(C).
    13. Chao Fang & Piao Dong & Yi-Ping Fang & Enrico Zio, 2020. "Vulnerability analysis of critical infrastructure under disruptions: An application to China Railway High-speed," Journal of Risk and Reliability, , vol. 234(2), pages 235-245, April.
    14. Jingjing Kong & Slobodan P. Simonovic, 2019. "Probabilistic Multiple Hazard Resilience Model of an Interdependent Infrastructure System," Risk Analysis, John Wiley & Sons, vol. 39(8), pages 1843-1863, August.
    15. Bellè, Andrea & Abdin, Adam F. & Fang, Yi-Ping & Zeng, Zhiguo & Barros, Anne, 2023. "A resilience-based framework for the optimal coupling of interdependent critical infrastructures," Reliability Engineering and System Safety, Elsevier, vol. 237(C).
    16. Zhao, Taiyi & Tang, Yuchun & Li, Qiming & Wang, Jingquan, 2024. "Enhancing urban system resilience to earthquake disasters: Impact of interdependence and resource allocation," International Journal of Critical Infrastructure Protection, Elsevier, vol. 45(C).
    17. Hausken, Kjell, 2017. "Defense and attack for interdependent systems," European Journal of Operational Research, Elsevier, vol. 256(2), pages 582-591.
    18. Bellè, Andrea & Abdin, Adam F. & Fang, Yi-Ping & Zeng, Zhiguo & Barros, Anne, 2023. "A data-driven distributionally robust approach for the optimal coupling of interdependent critical infrastructures under random failures," European Journal of Operational Research, Elsevier, vol. 309(2), pages 872-889.
    19. 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.
    20. Hassan Al-Zarooni & Hamdi Bashir, 0. "An integrated ISM fuzzy MICMAC approach for modeling and analyzing electrical power system network interdependencies," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 0, pages 1-23.

    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:spr:jglopt:v:74:y:2019:i:4:d:10.1007_s10898-018-0703-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.