Sven Malama

Transportation networks play a crucial role in society by enabling the smooth movement of people and goods during regular times and acting as arteries for evacuations during catastrophes and natural disasters. Identifying the critical road segments in a large and complex network is essential for planners and emergency managers to enhance the network’s efficiency, robustness, and resilience to such stressors. We propose a novel approach to rapidly identify critical and vital network components (road segments in a transportation network) for resilience improvement or post-disaster recovery. We pose the transportation network as a graph with roads as edges and intersections as nodes and deploy a Graph Neural Network (GNN) trained on a broad range of network parameter changes and disruption events to rank the importance of road segments. The trained GNN model can rapidly estimate the criticality rank of individual road segments in the modified network resulting from an interruption. We address two main limitations in the existing literature that can arise in capital planning or during emergencies: ranking a complete network after changes to components and addressing situations in post-disaster recovery sequencing where some critical segments cannot be recovered. Importantly, our approach overcomes the computational overhead associated with the repeated calculation of network performance metrics, which can limit its use in large networks. To highlight scenarios where our method can prove beneficial, we present examples of synthetic graphs and two real-world transportation networks. Through these examples, we show how our method can support planners and emergency managers in undertaking rapid decisions for planning infrastructure hardening measures in large networks or during emergencies, which otherwise would require repeated ranking calculations for the entire network.

Many networks, such as transportation, power, and water distribution, can be represented as graphs. Crucial challenge in graph representations is identifying the importance of graph edges and their influence on overall network efficiency and information flow performance. For example, important edges in a transportation network are those roads that, when affected, will significantly alter the network's overall efficiency. Commonly used approach to finding such important edges is ``edge betweenness centrality'' (EBC), an edge ranking measure to determine the influential edges of the graph based on connectivity and information spread. Computing the EBC utilizing the common Brandes algorithm involves calculating the shortest paths for every node pair, which can be computationally expensive and restrictive, especially for large graphs. Changes in the graph parameters, e.g., in the edge weight or the addition and deletion of nodes or edges, require the recalculation of the EBC. As the main contribution, we propose an approximate method to estimate the EBC using a Graph Neural Network (GNN), a deep learning-based approach. We show that it is computationally efficient compared to the conventional method, especially for large graphs. The proposed method of GNN-based edge ranking is evaluated on several synthetic graphs and a real-world transportation data set. We show that this framework can estimate the approximate edge ranking much faster compared to the conventional method. This approach is inductive, i.e., training and testing are performed on different sets of graphs with varying numbers of nodes and edges. The proposed method is especially suitable for applications on large-scale networks when edge information is desired, for example, in urban infrastructure improvement projects, power, and water network resilience analyses, and optimizing resource allocations in engineering networks.