Widget Image
Widget Image
Widget Image
© Asia Pacific Fire & MDM Publishing Ltd.
Location of Tokyo Subway, Japan.

Can graph theory techniques help with emergency response

To understand how components of our built environment and society will fare during a disaster, we first need to know the interconnectedness of network systems and the role each component plays.

Transportation, communication, power, water and sewage are the infrastructure and services critical to modern societies for day-to-day living, the movement of goods and services, and disaster response and recovery. These lifeline networks are vulnerable to disruption from numerous shocks, including structural and technological failure, human error or targeted attack and, our interest here, natural hazard events.

Lifelines comprise a large number of interconnected components, often spanning extensive geographic areas and, in some cases, multiple urban centres, states and international boarders (Guikema 2009). Feedback loops and complex topologies created by lifeline interdependencies can trigger and propagate disruptions in a variety of ways that are difficult to foresee (Rinaldi et al. 2001). Impacts may be felt not just locally but nationally or even globally.

Recent examples include the November 2016 7.8 magnitude Kaikoura earthquake in New Zealand, which triggered landslides that blocked the main highway, State Highway 1, and the South Island Main Trunk railway, isolating the popular tourist destination of Kaikoura for over a month. In September 2016, Southern Australian was hit by a severe storm that knocked over 22 transmission poles and damaged a number of generation facilities. This resulted in a statewide power outage, leaving 1.67 million South Australian residents without electricity for nearly 12 hours, disrupting businesses and affecting other lifelines operation such as communications and traffic signals. With more widespread consequences, the 2011 Thailand floods created problems for the global car and computer hardware industries.

Here we explore Graph Theory as a means of studying lifeline disruption using a hypothetical flooding incident on the Tokyo Subway network, Japan. The Tokyo Subway is used as an example because its configuration of stations and passenger numbers are well known. The subway is also located in a region susceptible to a range of natural perils.

Fig. 1 Example of a graph with six nodes and eleven edges.

Fig. 1 Example of a graph with six nodes and eleven edges.

Graph theory simplifies complex systems into nodes and edges to identify network structure, and the processes within (Fig. 1). Its foundations go back to the mathematician Euler, who, in 1735, proved that it was impossible to take a walk through the medieval town of Königsberg, Russia, and visit each part of town by crossing each of its seven bridges only once (Barabási 2002). In recent decades graph theory has been used to investigate a wide range of systems from the World Wide Web to social networks. Current applications of graph theory for lifeline network analysis focus on network structure and robustness to random failure and targeted attack (Albert et al., 2004; Crucitti et al., 2004; Koç et al., 2014; Angeloudis and Fisk, 2006; Derrible and Kennedy, 2010; Cardillo et al., 2013).

Fig. 2 Graph representation of the Tokyo Subway, Japan. Hypothetical inundation hazard footprint is indicated in blue and network components that coincide with the footprint are highlighted in red.

Fig. 2 Graph representation of the Tokyo Subway, Japan. Hypothetical inundation hazard footprint is indicated in blue and network components that coincide with the footprint are highlighted in red.

The Tokyo Subway (including Tokyo Metro and Toei Subway) services nearly nine million passengers daily. Despite its reputed reliability and punctuality, the Tokyo subway is still susceptible to failure and disruption, such as the Sarin attack in 1995 (Okumura et al. 1998), and suffers from congestion during peak commuting hours. It consists of 214 stations (nodes) and 273 track connections (edges). For this analysis, the subway stations were weighted by average daily passenger numbers and track connections by travel time. The network was subjected to a hypothetical inundation scenario (Fig. 2). Graph theory techniques were used to analyse basic network operations before and after component failure. For simplicity all components within the hazard footprint were deemed unusable.

Fig. 3 Change in shortest path between Tsukijishijo and Ningyocho stations after inundated stations and connections were deleted. Travel time between these two stations increased by 13 minutes.

Fig. 3 Change in shortest path between Tsukijishijo and Ningyocho stations after inundated stations and connections were deleted. Travel time between these two stations increased by 13 minutes.

In this scenario 26% of the network was inundated (including 56 stations), potentially impacting over 5 million daily passengers across 9 of the 23 Special Wards of the Tokyo Metropolitan Prefecture (Table 1). It also isolated another 11 stations, potentially blocking 290,000 passengers from accessing the remaining operational section of the network. Graph theory techniques were used to navigate through the network and determine shortest paths between two nodes. Throughout the remaining operational section of the subway, assuming current travel times on individual connections, there was an average increase in total travel time between locations of approximately two and a half minutes, with the maximum being 13 minutes (Fig. 3). Other graph theory measures were used to determine a node’s importance or centrality. Betweenness is one such measure, which measures how many times a station is a connector along the shortest path between two other stations (Fig. 4).

Fig. 4 Station ‘betweenness’ before and after deletion of inundated components. Warmer colours indicate high scores and cooler colours indicate low scores.

Fig. 4 Station ‘betweenness’ before and after deletion of inundated components. Warmer colours indicate high scores and cooler colours indicate low scores.

The importance of network analysis for disaster response and recovery is in identifying at risk critical infrastructure and determining the potential disruptions caused by service failure. These measures can help determine accessibility for emergency responders or routes for evacuation and be used to identify which infrastructure components should be protected and/or rebuilt. The utilisation of graph theory to analyse lifeline network disruption can help us better understand the extent of its reach.

For more information, email emma.a.singh@gmail.com

Share With:
Rate This Article

Emma Singh is a PhD student with Risk Frontiers and the Department of Environmental Sciences at Macquarie University in Sydney. Emma is investigating critical infrastructure disruption during natural hazard events, with a particular interest in the implications of network failure for emergency response during and community recovery after a disaster.