Graph Theory Approach to the Vulnerability of Transportation Networks
Abstract
:1. Introduction
- Energy;
- Information and communication technology;
- Agriculture (water, food);
- Finance, public and legal order, and safety;
- Infrastructure bottlenecks—can be the outcome of chronic or temporary conditions (e.g., factors: climate change, traffic expansions, such as a bridge or a port).
- Regulations bottlenecks—can be the results of regulations that delay goods movement for security or safety inspections (in international transport: custom procedures for passengers and freight).
- Supply chain bottlenecks—can be results of specific tasks and procedures in supply chain management (labor availability—work shifts may impose time-dependent capacity shortages; some firms may create bottlenecks on purpose as a rent-seeking strategy since they control key elements of the supply chain; different information exchange protocols can create delays in information processing, and therefore, delays in shipments).
- Minimize the distance to the critical points for the citizens under a fixed number of them;
- Reduce the number of base stations needed to support all of its users;
- Select the minimum number of representatives necessary for the overall monitoring of communication networks.
2. Materials and Methods
2.1. General Assumptions
2.2. Current Indicators for Transportation Network Description
- Express of the relationship between the values of these parameters and the structure of the network;
- Comparing the different transportation networks at certain points in time;
- Comparing the development of transport networks at different times.
- Network level:
- Cost, which represents the total length of the network measured in real transport distances.
- Detour index is a measure of the efficiency of a transport network in terms of how well it overcomes distance or the friction of distance.
- Network density measures the territorial occupation of a transport network in terms of km of links per square kilometers of surface.
- Pi index describes the relationship between the total length of the graph and the distance along its diameter.
- Eta index describes average length per link.
- Theta Index measures the function of a node, which is the average amount of traffic per intersection.
- Alpha index is a measure of connectivity which evaluates the number of cycles in a graph in comparison with the maximum number of cycles.
- Beta index is a measure of the level of connectivity in a graph and is expressed by the relationship between the number of links e over the number of nodes v.
- Gamma index is a measure of connectivity that considers the relationship between the number of observed links and the number of possible links.
- Node level:
- Order (degree) of a node (o). The number of its attached links; it is a simple, but effective measure of nodal importance.
- Koenig number (or associated number, eccentricity) is a measure of fairness based on the number of links needed to reach the most distant node in the graph.
- Hub dependence is a measure of node vulnerability that is the share of the highest traffic link in total traffic (weighted degree).
- Average nearest neighbors degree is a measure of neighborhoods indicating the type of environment in which the node situates.
- Cohesion index (ci) for a given edge : this index measures the ratio between the number of common neighbors connected to nodes u and v and the total number of their neighbors.
- Within-module degree (z-score) describes how well connected a node is to other nodes in the same module (or cluster, community).
- The participation coefficient allows one to compare the number of links (order, degree) of node u to nodes in all clusters with its number of links within its own cluster.
- Shimbel index (or Shimbel distance, nodal accessibility, nodality) is a measure of accessibility representing the sum of the length of all shortest paths connecting all other nodes in the graph.
- Betweenness centrality (or shortest-path betweenness) is a measure of accessibility that is the number of times a node is crossed by shortest paths in the graph.
2.3. Selected Domination Concepts in Graph Theory
- The weighted domination number of is the minimum weight of a set such that every vertex is in D or has a neighbor in D;
- The weighted independent domination number of of is the minimum weight of a set such that no two vertices of are connected by any edge of .
Algorithm 1 Dominating-set-1. |
|
Algorithm 2 Dominating-set-2. |
|
2.4. Basic Concepts of Vulnerability in Transport
3. Results
3.1. Structural Transportation Network Vulnerability
Algorithm 3 Minimal-vertex-dominating-set. |
|
3.2. Weighted Structural Transportation Vulnerability
Algorithm 4 Weighted-domination-number. |
|
3.3. Customer Vulnerability
4. Discussion
- Number of critical nodes = domination number;
- Number of critical edges = edge-domination number;
- Topological (structural) vulnerability of transport network = bondage-connected number;
- Weighted structural vulnerability of transport network = weighted bondage-connected number;
- Node-bottlenecks of transport network = dominating set, and weighted dominating set;
- Arc-bottlenecks of transport network = edge-dominating set, and weighted edge-dominating set;
- Consumer vulnerability = domination subdivision number.
- Dynamic—after removing the arcs in graph, the new minimal dominating set has to be found;
- Static—after removing the arcs in graph, the new minimal dominating set is the extension of the old one.
5. Conclusions
Funding
Conflicts of Interest
References
- Croatian Parliament. Croatian Law on Critical Infrastructures; Official Gazette: Zagreb, Croatia, 2013. [Google Scholar]
- European Union; European Commission. Communication from the Commission on Critical Infrastructure Protection in the Fight Against Terrorism; COM (2004)702 Final; European Union; European Commission: Brussels, Belgium, 2004. [Google Scholar]
- European Union; European Commission. Green Paper on a European Program for Critical Infrastructure Protection; COM (2005)576 Final; European Union; European Commission: Brussels, Belgium, 2005. [Google Scholar]
- European Union; European Council. Council Directive 2008/114/EC of 8 December 2008 on the Identification and Designation of European Critical Infrastructures and the Assessment of the Need to Improve Their Protection; European Union; European Council: Brussels, Belgium, 2008. [Google Scholar]
- US President’s Commission on Critical Infrastructure Protection. Critical Foundations: Protecting America’s Infrastructures; US President’s Commission on Critical Infrastructure Protection: Washington, DC, USA, 1997. [Google Scholar]
- Kolowrocki, K.; Soszyńska-Budny, J. Reliability and Safety of Complex Technical Systems and Processes, Modeling-Identification-Prediction-Optimization; Springer Series in Reliability Engineering; Springer: Berlin/Heidelberg, Germany, 2011. [Google Scholar]
- Borkowski, P. Inference engine in an intelligent ship course-keeping system. Comput. Intell. Neurosci. 2017, 2017. [Google Scholar] [CrossRef] [Green Version]
- Blokus, A.; Kolowrocki, K. Reliability and maintenance strategy for systems with aging-dependent components. Qual. Reliab. Eng. Int. 2019, 35, 2709–2731. [Google Scholar] [CrossRef]
- Bogalecka, M.; Kolowrocki, K.; Soszynska-Budny, J. A General Approach to Critical Infrastructure Accident Consequences Analysis. In Proceedings of the International Conference on Numerical Analysis and Applied Mathematics 2015 (ICNAAM-2015), Rhodes, Greece, 23–29 September 2015. [Google Scholar]
- Levina, E.; Tirpak, D. Adaptation to Climate Change: Key Terms; Organisation for Economic Co-operation and Development (OECD): Paris, France, 2006. [Google Scholar]
- US Department of Homeland Security. National Infrastructure Protection Plan (NIPP) 2013: Partnering for Critical Infrastructure Security and Resilience; US Department of Homeland Security: Washington, DC, USA, 2013. [Google Scholar]
- Kolowrocki, K.; Soszynska-Budny, J.; Torbicki, M. Critical Infrastructure Impacted by Climate Change Safety and Resilience Indicators. In Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management (IEEE IEEM), Bangkok, Thailand, 16–19 December 2018; pp. 986–990. [Google Scholar]
- Borkowski, P. Numerical modeling of wave disturbances in the process of ship movement control. Algorithms 2018, 11, 130. [Google Scholar] [CrossRef] [Green Version]
- Guze, S. Business Availability Indicators of Critical Infrastructures Related to the Climate-Weather Change. In Contemporary Complex Systems and Their Dependability, DepCoS-RELCOMEX 2018; Zamojski, W., Mazurkiewicz, J., Sugier, J., Walkowiak, T., Kacprzyk, J., Eds.; Springer: Cham, Switzerland, 2019. [Google Scholar]
- Newell, G.F. Traffic Flow on Transportation Networks; Series in Transportation Studies; MIT Press: London, UK, 1980. [Google Scholar]
- Blokus-Roszkowska, A.; Smolarek, L. Maritime traffic flow simulation in the Intelligent Transportation Systems. In Proceedings of the European Safety and Reliability Conference (Esrel): Safety and Reliability: Methodology and Applications, Wrocław, Polska, 14–18 September 2014; pp. 265–274. [Google Scholar]
- Rodrigue, J.P.; Comtois, C.; Slack, B. The Geography of transport Systems, 4th ed.; Routledge: London, UK, 2017. [Google Scholar]
- Cascetta, E. Transportation Systems in Transportation Systems Engineering: Theory and Methods; Springer: Boston, MA, USA, 2001. [Google Scholar]
- Haładyn, S.M.; Restel, F.J.; Wolniewicz, L. Method for railway timetable evaluation in terms of random infrastructure load. In Proceedings of the Fourteenth International Conference on Dependability of Computer Systems DepCoS-RELCOMEX, Brunów, Poland, 1–5 July 2019. [Google Scholar]
- Friedrich, J.; Restel, F.J. A fuzzy approach for evaluation of reconfiguration actions after unwanted events in the railway system. In Proceedings of the Fourteenth International Conference on Dependability of Computer Systems DepCoS-RELCOMEX, Brunów, Poland, 1–5 July 2019; pp. 195–204. [Google Scholar]
- Restel, F.J. Train punctuality model for a selected part of railway transportation system. In Safety, Reliability and Risk Analysis: Beyond the Horizon: Proceedings of the European Safety and Reliability Conference, Amsterdam, The Netherlands, 29 September–2 October 2013; CRC Press: Steenbergen, The Netherlands, 2014; pp. 3013–3019. [Google Scholar]
- Ding, X.; Guan, S.; Sun, D.J.; Jia, L. Short Turning Pattern for Relieving Metro Congestion during Peak Hours. Eur. Transp. Res. Rev. 2018, 2018, 1–11. [Google Scholar]
- Harrary, F. Graph Theory; Addison-Wesley: Boston, MA, USA, 1969. [Google Scholar]
- Van Leeuwen, J. Chapter 10—Graph Algorithms Book–Algorithms and Complexity. In Handbook of Theoretical Computer Science; MIT Press: Cambridge, MA, USA, 1990; Volume 525, pp. 527–631. [Google Scholar]
- Gross, J.L.; Yellen, J. Handbook of Graph Theory; CRC Press: Boca Raton, FL, USA, 2004; ISBN 978-1-58488-090-5. [Google Scholar]
- Kansky, K.J. The Structure of Transport Networks; University of Chicago: Chicago, IL, USA, 1963. [Google Scholar]
- Haynes, T.W.; Hedetniemi, S.; Slater, P. Fundamentals of Domination in Graphs; CRC Press: Boca Raton, FL, USA, 1998. [Google Scholar]
- Velammal, S. Studies in Graph Theory: Covering, Independence, Domination and Related Topics. Ph.D. Thesis, Manonmaniam Sundaranar University, Tirunelveli, India, 1997. [Google Scholar]
- Haynes, T.W.; Hedetniemi, M.; Hedetniemi, T. Domination and independence subdivision numbers of graphs. Discuss. Math. Graph Theory 2000, 20, 271–280. [Google Scholar] [CrossRef] [Green Version]
- Guze, S. Graph Theory Approach to Transportation Systems Design and Optimization. Int. J. Mar. Navig. Saf. Sea Transp. 2014, 8, 571–578. [Google Scholar] [CrossRef] [Green Version]
- Guze, S. An application of the selected graph theory domination concepts to transportation networks modelling. Sci. J. Marit. 2017, 52, 97–102. [Google Scholar]
- Bhattacharya, A.; Vijayakumar, G.R. Effect of edge-subdivision on vertex-domination in a graph. Discuss. Math. Graph Theory 2002, 22, 335–347. [Google Scholar] [CrossRef] [Green Version]
- Walikar, H.B.; Acharya, B.D.; Sampathkumar, E. Recent Developments in the Theory of Domination in Graphs; Mehta Research Institute of Mathematics: Allahabad, India, 1979; Volume 1, Available online: https://www.tib.eu/en/search/id/TIBKAT%3A014901056/Recent-developments-in-the-theoryof-domination/ (accessed on 11 December 2019).
- Parekh, A.K. Analysis of Greedy Heuristic for Finding Small Dominating Sets in Graphs. Inf. Process. Lett. 1991, 39, 237–240. [Google Scholar] [CrossRef] [Green Version]
- Ruan, L.; Du, H.; Jia, X.; Wu, W.; Li, Y.; Ko, K.-I. A greedy approximation for minimum connected dominating sets. Theor. Comput. Sci. 2004, 329, 325–330. [Google Scholar] [CrossRef] [Green Version]
- Topp, J. Graph with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices. Discret. Math. 1993, 121, 199–210. [Google Scholar] [CrossRef] [Green Version]
- Fink, J.F.; Jacobson, M.S.; Kinch, L.F.; Roberts, J. The bondage number of graph. Discret. Math. 1990, 86, 47–57. [Google Scholar] [CrossRef] [Green Version]
- Hartnell, B.L.; Rall, D.F. Bounds on the bondage number of a graph. Discret. Math. 1994, 128, 173–177. [Google Scholar] [CrossRef] [Green Version]
- Detalaff, M.; Raczek, J.; Topp, J. Domination Subdivision and Domination Multisubdivision Numbers of Graphs. Discuss. Math. Graph Theory 2019, 39, 829–839. [Google Scholar] [CrossRef]
- Berdica, K. An introduction to road vulnerability: What has been done, is done and should be done. Transp. Policy 2002, 9, 117–127. [Google Scholar] [CrossRef]
- Appert, M.; Chapelon, L. Measuring Urban Road Network Vulnerability using Graph Theory: The Case of Montpellier’s Road Network. Working Paper. 2013, pp. 1–8. Available online: https://halshs.archives-ouvertes.fr/halshs-00841520/document (accessed on 30 November 2019).
- Berdica, K.; Eliasson, J. Regional accessibility analysis from a vulnerability perspectiv. In Proceedings of the Second International Symposium on Transportation Network Reliability (INSTR), Christchurch and Queenstown, New Zealand, 20–24 August 2004; pp. 89–94. [Google Scholar]
- D’Este, G.M.; Taylor, M.A.P. Network vulnerability: An approach to reliability analysis at the level of national strategic transport networks. In The Network Reliability of Transport, Emerald Group Publishing Limited; Bell, M., Iida, Y., Eds.; Pergamon: Oxford, UK, 2003; pp. 23–44. [Google Scholar] [CrossRef]
- Du, Z.P.; Nicholson, A. Degradable transportation systems: Sensitivity and reliability analysis. Transp. Res. Part Methodol. 1997, 31, 225–237. [Google Scholar] [CrossRef]
- Husdal, J. Reliability and vulnerability versus cost and benefits. In Proceedings of the Second International Symposium on Transportation Network Reliability (INSTR), Christchurch, New Zealand, 20–24 August 2004; pp. 182–188. [Google Scholar]
- Immers, L.H.; Stada, J.E.; Yperman, I.; Bleukx, A. Robustness and resilience of transportation networks. In Proceedings of the 9th International Scientific Conference MOBILITA, Bratislava, Slovenia, 6–7 May 2004. [Google Scholar]
- Jenelius, E.; Petersen, T.; Mattsson, L. Importance and exposure in road network vulnerability analysis. Transp. Res. Part A 2006, 40, 537–560. [Google Scholar] [CrossRef]
- Reggiani, A.; Nijkamp, P.; Lanzi, D. Transport resilience and vulnerability: The role of connectivity. Transp. Res. 2015, 81, 4–15. [Google Scholar] [CrossRef]
- Sarewitz, D.; Pielke, R., Jr.; Keykhah, M. Vulnerability and risk: Some thoughts from a political and policy perspective. Risk Anal. 2003, 23, 805–810. [Google Scholar] [CrossRef] [Green Version]
- Sun, D.; Zhao, Y.; Lu, Q.-C. Vulnerability Analysis of Urban Rail Transit Networks: A Case Study of Shanghai, China. Sustainability 2015, 7, 6919–6936. [Google Scholar] [CrossRef] [Green Version]
- Sun, D.; Guan, S. Measuring vulnerability of Urban Metro Network from Line Operation Perspective. Transp. Res. 2016, 94, 348–359. [Google Scholar] [CrossRef]
- Estrada, E. Network robustness to targeted attacks. The interplay of expansibility and degree distribution. Eur. Phys. J. 2006, 52, 563–574. [Google Scholar] [CrossRef]
- Latora, V.; Marchiori, M. Vulnerability and protection of infrastructure networks. arXiv 2004, arXiv:cond-mat/0407491v1. [Google Scholar] [CrossRef] [PubMed] [Green Version]
- Hollnagel, E.; Woods, D.D.; Leveson, N. Resilience Engineering: Concepts and Percepts; Ashgate Publishing Limited: Aldershot, UK, 2006. [Google Scholar]
- Patriarca, R.; Bergström, J.; Di Gravio, G.; Costantino, F. Resilience engineering: Current status of the research and future challenges. Saf. Sci. 2018, 102, 79–100. [Google Scholar] [CrossRef]
© 2019 by the author. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Guze, S. Graph Theory Approach to the Vulnerability of Transportation Networks. Algorithms 2019, 12, 270. https://0-doi-org.brum.beds.ac.uk/10.3390/a12120270
Guze S. Graph Theory Approach to the Vulnerability of Transportation Networks. Algorithms. 2019; 12(12):270. https://0-doi-org.brum.beds.ac.uk/10.3390/a12120270
Chicago/Turabian StyleGuze, Sambor. 2019. "Graph Theory Approach to the Vulnerability of Transportation Networks" Algorithms 12, no. 12: 270. https://0-doi-org.brum.beds.ac.uk/10.3390/a12120270