IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0219658.html
   My bibliography  Save this article

A deterministic approach for rapid identification of the critical links in networks

Author

Listed:
  • Rostislav Vodák
  • Michal Bíl
  • Tomáš Svoboda
  • Zuzana Křivánková
  • Jan Kubeček
  • Tomáš Rebok
  • Petr Hliněný

Abstract

We introduce a rapid deterministic algorithm for identification of the most critical links which are capable of causing network disruptions. The algorithm is based on searching for the shortest cycles in the network and provides a significant time improvement compared with a common brute-force algorithm which scans the entire network. We used a simple measure, based on standard deviation, as a vulnerability measure. It takes into account the importance of nodes in particular network components. We demonstrate this approach on a real network with 734 nodes and 990 links. We found the worst scenarios for the cases with and without people living in the nodes. The evaluation of all network breakups can provide transportation planners and administrators with plenty of data for further statistical analyses. The presented approach provides an alternative approach to the recent research assessing the impacts of simultaneous interruptions of multiple links.

Suggested Citation

  • Rostislav Vodák & Michal Bíl & Tomáš Svoboda & Zuzana Křivánková & Jan Kubeček & Tomáš Rebok & Petr Hliněný, 2019. "A deterministic approach for rapid identification of the critical links in networks," PLOS ONE, Public Library of Science, vol. 14(7), pages 1-18, July.
    • Handle: RePEc:plo:pone00:0219658
    DOI: 10.1371/journal.pone.0219658
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0219658
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0219658&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0219658?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
    ---><---

    References listed on IDEAS

    as
    1. Michael Taylor & Somenahalli Sekhar & Glen D'Este, 2006. "Application of Accessibility Based Methods for Vulnerability Analysis of Strategic Road Networks," Networks and Spatial Economics, Springer, vol. 6(3), pages 267-291, September.
    2. Sohn, Jungyul, 2006. "Evaluating the significance of highway network links under the flood damage: An accessibility approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 40(6), pages 491-506, July.
    3. Berdica, Katja, 2002. "An introduction to road vulnerability: what has been done, is done and should be done," Transport Policy, Elsevier, vol. 9(2), pages 117-127, April.
    4. Bell, Michael G.H. & Kurauchi, Fumitaka & Perera, Supun & Wong, Walter, 2017. "Investigating transport network vulnerability by capacity weighted spectral analysis," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 251-266.
    5. Michael A. P. Taylor, 2008. "Critical Transport Infrastructure in Urban Areas: Impacts of Traffic Incidents Assessed Using Accessibility‐Based Network Vulnerability Analysis," Growth and Change, Wiley Blackwell, vol. 39(4), pages 593-616, December.
    6. Marion Michael-Leiba & Fred Baynes & Greg Scott & Ken Granger, 2003. "Regional landslide risk to the Cairns community," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 30(2), pages 233-249, October.
    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. Iliopoulou, Christina & Makridis, Michail A., 2023. "Critical multi-link disruption identification for public transport networks: A multi-objective optimization framework," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 626(C).
    2. Liang Jia & Saini Yang & Weiping Wang & Xinlong Zhang, 2022. "Impact analysis of highways in China under future extreme precipitation," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 110(2), pages 1097-1113, January.
    3. Ahmad Mohamad El-Maissi & Sotirios A. Argyroudis & Fadzli Mohamed Nazri, 2020. "Seismic Vulnerability Assessment Methodologies for Roadway Assets and Networks: A State-of-the-Art Review," Sustainability, MDPI, vol. 13(1), pages 1-31, December.

    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. Jenelius, Erik & Mattsson, Lars-Göran, 2012. "Road network vulnerability analysis of area-covering disruptions: A grid-based approach with case study," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(5), pages 746-760.
    2. Nogal, Maria & Morales Nápoles, Oswaldo & O’Connor, Alan, 2019. "Structured expert judgement to understand the intrinsic vulnerability of traffic networks," Transportation Research Part A: Policy and Practice, Elsevier, vol. 127(C), pages 136-152.
    3. Victor Cantillo & Luis F. Macea & Miguel Jaller, 2019. "Assessing Vulnerability of Transportation Networks for Disaster Response Operations," Networks and Spatial Economics, Springer, vol. 19(1), pages 243-273, March.
    4. Muriel-Villegas, Juan E. & Alvarez-Uribe, Karla C. & Patiño-Rodríguez, Carmen E. & Villegas, Juan G., 2016. "Analysis of transportation networks subject to natural hazards – Insights from a Colombian case," Reliability Engineering and System Safety, Elsevier, vol. 152(C), pages 151-165.
    5. Demirel, Hande & Kompil, Mert & Nemry, Françoise, 2015. "A framework to analyze the vulnerability of European road networks due to Sea-Level Rise (SLR) and sea storm surges," Transportation Research Part A: Policy and Practice, Elsevier, vol. 81(C), pages 62-76.
    6. Jenelius, Erik, 2010. "User inequity implications of road network vulnerability," The Journal of Transport and Land Use, Center for Transportation Studies, University of Minnesota, vol. 2(3), pages 57-73.
    7. Li, Tao & Rong, Lili & Yan, Kesheng, 2019. "Vulnerability analysis and critical area identification of public transport system: A case of high-speed rail and air transport coupling system in China," Transportation Research Part A: Policy and Practice, Elsevier, vol. 127(C), pages 55-70.
    8. Yu Miao & Anning Ni, 2019. "Vulnerability Analysis of Intercity Multimode Transportation Networks; A Case Study of the Yangtze River Delta," Sustainability, MDPI, vol. 11(8), pages 1-16, April.
    9. Rodríguez-Núñez, Eduardo & García-Palomares, Juan Carlos, 2014. "Measuring the vulnerability of public transport networks," Journal of Transport Geography, Elsevier, vol. 35(C), pages 50-63.
    10. Ortega, Emilio & Martín, Belén & Aparicio, Ángel, 2020. "Identification of critical sections of the Spanish transport system due to climate scenarios," Journal of Transport Geography, Elsevier, vol. 84(C).
    11. Taylor, Michael A.P. & Susilawati,, 2012. "Remoteness and accessibility in the vulnerability analysis of regional road networks," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(5), pages 761-771.
    12. Sugiura, Satoshi & Chen, Anthony, 2021. "Vulnerability analysis of cut-capacity structure and OD demand using Gomory-Hu tree method," Transportation Research Part B: Methodological, Elsevier, vol. 153(C), pages 111-127.
    13. 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.
    14. Paramet Luathep & Agachai Sumalee & H. Ho & Fumitaka Kurauchi, 2011. "Large-scale road network vulnerability analysis: a sensitivity analysis based approach," Transportation, Springer, vol. 38(5), pages 799-817, September.
    15. Juan Carlos García-Palomares & Javier Gutiérrez & Juan Carlos Martín & Borja Moya-Gómez, 2018. "An analysis of the Spanish high capacity road network criticality," Transportation, Springer, vol. 45(4), pages 1139-1159, July.
    16. Allan Peñafiel Mera & Chandra Balijepalli, 2020. "Towards improving resilience of cities: an optimisation approach to minimising vulnerability to disruption due to natural disasters under budgetary constraints," Transportation, Springer, vol. 47(4), pages 1809-1842, August.
    17. Lu, Qing-Chang & Xu, Peng-Cheng & Zhang, Jingxiao, 2021. "Infrastructure-based transportation network vulnerability modeling and analysis," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 584(C).
    18. Ahmad Mohamad El-Maissi & Sotirios A. Argyroudis & Fadzli Mohamed Nazri, 2020. "Seismic Vulnerability Assessment Methodologies for Roadway Assets and Networks: A State-of-the-Art Review," Sustainability, MDPI, vol. 13(1), pages 1-31, December.
    19. Gu, Yu & Chen, Anthony & Xu, Xiangdong, 2023. "Measurement and ranking of important link combinations in the analysis of transportation network vulnerability envelope buffers under multiple-link disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 167(C), pages 118-144.
    20. Jenelius, Erik, 2009. "Network structure and travel patterns: explaining the geographical disparities of road network vulnerability," Journal of Transport Geography, Elsevier, vol. 17(3), pages 234-244.

    More about this item

    Statistics

    Access and download statistics

    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:plo:pone00:0219658. 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: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    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.