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.

CDV Transport Research Centre Brno Czech Republic

CERIT SC Institute of Computer Science Masaryk University Brno Czech Republic

CESNET Prague Czech Republic

Faculty of Informatics Masaryk University Brno Czech Republic

Faculty of Science Palacký University Olomouc Czech Republic

Zobrazit více v PubMed

Berdica K. An introduction to road vulnerability: what has been done, is done and should be done. Transport Policy. 2002;9: 117–127.

Taylor MAP, Sekhar SVC and D’Este GM. Application of Accessibility Based Methods for Vulnerability Analysis of Strategic Road Networks. Networks and Spatial Economics. 2006;6: 267–291.

Sohn J. Evaluating the significance of highway network links under flood damage: An accessibility approach. Transportation Research Part A: Policy and Practice. 2006;40: 491–506.

Taylor MAP. Critical transport infrastructure in urban areas: impacts of traffic incidents assessed using accessibility-based network vulnerability analysis. Growth Change. 2008;39(4): 593–616.

Bell MGH, Kuaruchi F, Perera S, Wong W. Investigating transport network vulnerability by capacity weighted spectral analysis. Transp. Res. Part B. 2017;99: 251–266.

Mattsson LG, Jenelius E. Vulnerability and resilience of transport systems–A discussion of recent research. Transportation Research Part A: Policy and Practice. 2015;81: 16–34.

Michael-Leiba M, Baynes F, Scott G, Granger K. Regional landslide risk to the Cairns community. Natural Hazards. 2003;30(2): 233–249.

Jaiswal P, van Westen CJ, Jetten V. Quantitative assessment of landslide hazard along transportation lines using historical records. Landslides. 2011;8(3): 279–291.

Bíl M, Kubeček J, Andrášik R. An epidemiological approach to determining the risk of road damage due to landslides. Natural Hazards 2014;73(3): 323–1335.

Bell MGH, Cassir C, Iida Y, Lam WHK. A sensitivity based approach to network reliability assessment. Proceedings of the 14th International Symposium on Transportation and Traffic Theory. Pergamon, Oxford. 1999; 283–300.

Qiao WX, Lu Y, Xiong CF, Haghani A. A game theory approach for the measurement of transport network vulnerability from the system prospective. Transportmetrica B: Transport Dynamics. 2004;2(3): 188–202.

Bíl M, Vodák R, Kubeček J, Bílová M, Sedoník J. Evaluating road network damage caused by natural disasters in the Czech Republic between 1997 and 2010. Transportation Research Part A: Policy and Practice. 2015;80: 90–103.

Dalziell EP, Nicholson AJ. Risk and impact of natural hazards on a road network. ASCE Journal of Transportation Engineering. 2001;127(2): 159–166.

Jenelius E, Pettersen T, Mattson LG. Importance and exposure in road network vulnerability analysis. Transportation Research Part A: Policy and Practice. 2006;40: 537–560.

Jansuwan S, Chen A. Considering Perception Errors in Network Efficiency Measure: An Application to Bridge Importance Ranking in Degradable Transportation Networks. Transportmetrica A: Transport Science. 2015;11(9): 793–818.

Kim S, Yeo H. Evaluating link criticality of road network based on the concept of macroscopic fundamental diagram. Transportmetrica A: Transport Science. 2017;12(2): 162–193.

Iida Y, Wakabayashi H. An approximation method of terminal reliability of road network using partial minimal path and cut set. Proceedings of the Fifth World Conference on Transport Research. Yokohama, Japan. 1989;4: 367–380.

Du ZP, Nicholson AJ. Degradable transportation systems: sensitivity and reliability analysis, Transportation Research B: Methodological. 1997;31(3): 225–237.

Chen BY, Lam WHK, Sumalee A, Li Q, Li ZC. Vulnerability analysis for large-scale and congested road networks with demand uncertainty. Transportation Research Part A: Policy and Practice. 2012;46: 501–516.

Wang DZW, Liu H, Szeto WY, Chow AHF. Identification of critical combination of vulnerable links in transportation networks–a global optimisation approach. Transportmetrica A: Transport Science. 2016;12(4): 346–365.

Chen A, Yang H, Lo HK, Tang WH. Capacity Reliability of a Road Network: An Assessment Methodology and Numerical Results. Transportation Research Part B: Methodological. 2002;36(3): 225–252.

Knoop VL, Snelder M, van Zuylen HJ, Hoogendoorn SP. Link-level vulnerability indicators for real-world networks. Transportation Research Part A: Policy and Practice. 2012;46: 843–854.

Murray AT, Matisziw TC, Grubesic TH. A methodological overview of network vulnerability analysis. Growth Change. 2008;39(4): 573–592.

de Oliveira EL, Portugal LD, Junior W. Indicators of reliability and vulnerability: Similarities and differences in ranking links of a complex road system. Transportation Research Part A: Policy and Practice. 2016;88: 195–208.

Crucitti P, Latora V, Porta S. Centrality measures in spatial networks of urban streets. Physical Review E. 2006;73: 1–5. PubMed

Scott DM, Novak DC, Aultman-Hall L, Guo F. Network Robustness Index: A new method for identifying critical links and evaluating the performance of transportation networks. Journal of Transport Geography. 2006;14: 215–227.

Jenelius E. Network structure and travel patterns: explaining the geographical disparities of road network vulnerability. Journal of Transport Geography. 2009;17: 234–244.

Chen A, Yang C, Kongsomsaksakul S, Lee M. Network-based Accessibility Measures for Vulnerability Analysis of Degradable Transportation Networks. Networks and Spatial Economics. 2007;7: 241–256.

Matisziw TC, Murray AT. Modeling s-t path availability to support disaster vulnerability assessment of network infrastructure. Computers and Operations Research. 2009;36: 16–26.

Hong-ying Y, Li-gun X. Measuring the Structural Vulnerability of Road Network: A Network Efficiency Perspective. J. Shanghai Jiaotong Univ. (Sci.). 2010;15(6): 736–742.

Sullivan JL, Novak DC, Aultman-Hall L, Scott DM. Identifying critical road segments and measuring system-wide robustness in transportation networks with isolating links: A link-based capacity-reduction approach. Transportation Research Part A: Policy and Practice. 2010;44:323–336.

Watling D, Milne D, Clark S. Network impacts of a road capacity reduction: Empirical analysis and model predictions. Transportation Research Part A: Policy and Practice. 2012;46: 167–189.

Novak DC, Sullivan JL. A link-focused methodology for evaluating accessibility to emergency services. Decision Support Systems. 2014;57: 309–319.

Peeta S, Salman FS, Gunnec D, Viswanath K. Pre-disaster investment decisions for strengthening a highway network. Computers and Operations Research. 2010;37: 1708–1719.

Reggiani A. Network resilience for transport security: Some methodological considerations. Transport Policy. 2013;28: 63–68.

Bell MGH. The use of game theory to measure the vulnerability of stochastic networks. IEEE Transactions on Reliability. 2003;52(1): 6368.

Igor M, Filiposka S, Gramatikov S, Trajanov D, Kocarev L. Game Theoretic Approach for Discovering Vulnerable Links in Complex Networks. In Sobh T, Elleithy K Mahmood A (eds). Novel Algorithms and Techniques in Telecommunications and Networking; 2010; 211–216.

Berdica K, Mattsson LG. Vulnerability: A Model-based Case Study of the Road Network in Stockholm In: Murray AT, Grubesic TH (eds). Critical Infrastructure: Reliability and Vulnerability. Advances in Spatial Science. Springer, Berlin, Heidelberg: 2007; 81–106.

Jenelius E. User Inequity Implications of Road Network Vulnerability. Journal of Transport and Land Use. 2010;2(3): 57–73.

Jenelius E, Cats O. The Value of New Public Transport Links for Network Robustness and Redundancy. Transportmetrica A: Transport Science. 2015;11(9): 819–835.

Nagurney A, Qiang Q. Fragile Networks: Identifying Vulnerabilities and Synergies in an Uncertain World. Hoboken, NJ: John Wiley & Sons; 2009.

Ortigosa J, Menendez M. Traffic Performance on Quasi-grid Urban Structures. Cities. 2014;36: 18–27.

Snyder L, Daskin M. Models for Reliable Supply Chain Network Design In: Murray AT, Grubesic TH. (eds). Critical Infrastructure: Reliability and Vulnerability. Advances in Spatial Science. Springer, Berlin, Heidelberg: 2007; 257–289.

Taylor MAP, D’Este GM. Transport Network Vulnerability: A Method for Diagnosis of Critical Locations in Transport Infrastructure Systems In: Murray AT, Grubesic TH (eds). Critical Infrastructure: Reliability and Vulnerability. Advances in Spatial Science. Springer, Berlin, Heidelberg: 2007; 9–30.

Taylor MAP, Susilawati S. Remoteness and accessibility in the vulnerability analysis of regional road networks. Transportation Research Part A: Policy and Practice. 2012;46(5): 761–771. 10.1016/j.tra.2012.02.008 DOI

Taylor MAP. Vulnerability Analysis for Transportation Networks. Elsevier; Amsterdam, Netherlands: 2017.

D’Este GM, Taylor MAP. Network vulnerability: an approach to reliability analysis at the level of national strategic transport networks In: Iida Y, Bell MGH (eds). The Network Reliability of Transport. Pergamon-Elsevier, Oxford, 2003; 23–44.

Taylor MAP, D’Este GM. Critical infrastructure and transport network vulnerability: developing a method for diagnosis and assessment. In: Proceedings of Second International Symposium on Transportation Network Reliability. Christchurch and Queenstown, New Zealand. 2004; 96–102.

Bono F, Gutiérez E. A network-based analysis of the impact of structural damage on urban accesibility following a disaster: the case of the seismically damaged Port Au Prince and Carrefour urban road networks. Journal of Transport Geography. 2011;19: 1443–1455.

Chang SE, Nojima N. Measuring post-disaster transportation system performance: the 1995 Kobe earthquake in comparative perspective. Transportation Research Part A: Policy and Practice. 2001;35: 475494.

Jenelius E, Mattsson LG. Road network vulnerability analysis of area-covering disruptions: A grid-based approach with case study. Transportation Research Part A: Policy and Practice. 2012;46(5): 746–760.

Latora V, Marchiori M. How the science of complex networks can help developing strategies against terrorism. Chaos, Solitons and Fractals. 2004;20: 69–75.

Wang S, Hong L, Ouyang M, Zhang J, Chen X. Vulnerability analysis of interdependent infrastructure systems under edge attack strategies. Safety Science 2013;51: 328–337.

Xu X, Chen A, Yang C. An optimization approach for deriving upper and lower bounds of transportation network vulnerability under simultaneous disruptions of multiple links. Transportation Research Part C. 2018;94: 338–353.

Bell MGH. A game theory approach to measuring the performance reliability of transport networks, Transp. Res. Part B. 2000;34(6): 533–545.

Bell MGH, Cassir C. Risk-averse user equilibrium traffic assignment: an application of game theory. Transp. Res. Part B. 2002;36: 671–681.

Szeto WY, O’Brien L, O’Mahony M. Generalisation of risk averse traffic assignment In: Allsop RE, Bell MGH, Heydecker BG (eds). Transportation and Traffic Theory. Elsevier Science, Amsterdam: 2007; 127–153.

Nicholson A, Du ZP. Degradable transportation systems: an integrated equilibrium model. Transp. Res. Part B. 1997;31(3): 209–223.

Luathep P, Sumalee A, Ho HW, Kurauchi F. Large-scale road network vulnerability analysis: a sensitivity analysis based approach. Transportation. 2011;38(5): 799–817.

Burlet M, Goldschmidt O. A new and improved algorithm for the 3-cut problem. Operations Research Letters. 1997;21: 225–227.

Nagamochi H, Ibaraki T. A fast algorithm for computing minimum 3-way and 4-way cuts. Mathematical Programming, Ser. A. 2000;88: 507–520.

Nagamochi H, Katayama S, Ibaraki T. A faster algorithm for computing minimum 5-way and 6-way cuts in graphs. Journal of Combinatorial Optimization. 2000;4: 151–169.

Dinitz EA, Karzanov AV, Lomonosov MV. On the structure of a family of minimum weighted cuts in a graph. In: Fridman AA (Ed.). Studies in Discrete Optimization. 1976; 290–306. Nauka, Moscow, Original article in Russian, English translation from www.loc.gov or www.nrc.ca/cisti

Kamidoi Y, Wakabayashi S, Yoshida N. A divide-and-conquer approach to the minimum k-way cut problem. Algorithmica. 2002;32: 262–276.

Reinelt G, Wenger KM. Generating partitions of a graph into a fixed number of minimum weight cuts. Discrete Optimization. 2010;7: 1–12.

Papadimitriou CH, Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ. 1982.

Spielman DA. Spectral Graph Theory. 2015. http://www.cs.yale.edu/homes/spielman/561/.

Tsiatas A, Saniee I, Narayan O, Andrews M. Spectral analysis of communication networks using Dirichlet eigenvalues. Proceedings of the 22nd International Conference on World Wide Web. ACM. 2013:1297–1306.

Ma YY, Chiu YC, Yang XG. Urban traffic signal control network automatic partitioning using laplacian eigenvectors. 12th International IEEE Conference on Intelligent Transportation Systems. 2009: 1–5.

Martinez S, Chatterji G., Sun D, Bayen AM. A weighted-graph approach for dynamic airspace configuration. Proceedings of the AIAA Conference on Guidance, Navigation and Control (GNC). American Institute of Aeronautics and Astronautics. 2007.

Louail T, Lenormand M, Picornell M, Cantú OG, Herranz R, Frias-Martinez E, et al. Uncovering the spatial structure of mobility networks. Nature communications. 2015;6. PubMed

Gallotti R, Barthelemy M. The Multilayer Temporal Network of Public Transport in Great Britain, Scientific Data. 2015;2 10.1038/sdata.2014.56 PubMed DOI PMC

Lenormand M, Louail T, Cantú-Ros OG, Picornell M, Herranz R, Arias J M, et al. Influence of sociodemographic characteristics on human mobility. ArXiv. 2014;1411.7895v1. PubMed PMC

Lenormand M, Picornell M, Cantú-Ros OG, Tugores A, Louail T, Herranz R, et al. Cross-checking different sources of mobility information. PLoS One. 2014;9(8): e105184 10.1371/journal.pone.0105184 PubMed DOI PMC

Gottlich S, Klar A. Modeling and Optimization of Scalar Flows on Networks. In: Ambrosio L, Bressan A, Helbing D, Klar A, Zuazua E. Modelling and Optimisation Of Flows On Networks. Cetraro, Italy. 2009;2062: 395–461.

Lammer S, Kori H, Peters K, Helbing D. Decentralised control of material or traffic flows in networks using phase-synchronisation. Physica A: Statistical Mechanics and its Applications. 2006;363(1): 39–47.

Helbing D. Order and disorder in traffic and self-driven many-particle systems. In: Boccaletti S, Gluckman BJ, Kurths J, Pecora LM, Spano ML. Experimental Chaos. 2002;622: 239–250.

Traffic Helbing D. and related self-driven many-particle systems. Reviews of Modern Physics. 2001;73(4): 1067–1141.

Treiber M, Hennecke A, Helbing D. Congested traffic states in empirical observations and microscopic simulations. Physical Review E. 2000;62(2): 1805–1824. PubMed

Kurauchi F, Uno N, Sumalee A, Seto Y. Network evaluation based on connectivity vulnerability In: Lam HK, Wong SC, Lo HK (eds). Transportation and Traffic Theory 2009: Golden Jubilee. Springer; 2009; 637–649.

Garey MR, Johnson DS, Stockmeyer L. Some Simplified NP-Complete Graph Problems. Theoretical Compuer Science. 1976;1: 237–267.