Detecting Critical Streets in Road Networks Based on Topological Representation

Abstract

We provide a novel problem of analyzing geographical road networks from a perspective of identifying critical streets for vehicular evacuation. In vehicular evacuation behaviors during disasters and emergency situations, the shortest distance routes are not necessarily the best. Instead, routes that are easier to traverse can be more crucial, even if they involve detours. Furthermore, evacuation destinations need not be limited to conventional facilities or sites; wider and better maintained streets can also be suitable. Therefore, we focus on streets as basic units of road networks, and address the problem of finding critical streets in a geographical road network, considering a scenario in which people efficiently move from specified starting intersections located around their residences to designated goal streets, following the routes of easiest traversal. In this paper, we first model a road network as a vertex-weighted graph obtained from its topological representation, where vertices and edges represent streets and intersections between them, respectively. The weight of each vertex reflects its ease of traversal. Next, we extend a recently introduced edge-centrality measure, salience, for our problem, and propose a method of detecting critical streets based on the vertex-weighted graph of topological representation by incorporating the notion of damping factor into it. Using real-world road network obtained from OpenStreetMap, we experimentally reveal the characteristics of the proposed method by comparing it with several baselines.

1 Introduction

As the collection of large-scale geographical data, including transportation and road networks in urban areas, has progressed, researchers have been utilizing network science methodologies to analyze these geographical networks [4]. Conventionally, a geographical road network is modeled as an edge-weighted graph obtained from its geometric representation in network science, where vertices and edges represent intersections and road segments between adjacent intersections, respectively. The weight of each edge indicates the real distance of its corresponding road segment. Previous work employed the edge-weighted graphs of geometric representation, and analyzed the statistical properties of geographical road networks using traditional centrality measures such as degree, betweenness, and clustering coefficient [1]. However, Ma et al. [9] argued that from the perspective of predicting human behavior, it is essential for road network analysis to center around recognizable entities for people, such as streets, instead of fragmented road segments. Although there are various road categories such as “street”, narrower “way”, and broader “boulevard”, we refer to all these road categories as street for simplicity. Following this definition, it allows us to consider streets for vehicle evacuation both in terms of their narrowness and difficulty, as well as their breadth and ease of passage. This perspective holds the potential to enhance road network analysis. While there have been a handful of studies focusing on streets for road network analysis in the past [1, 9], to our knowledge, there have been no studies that specifically address the ease of passage on streets.

In network science, while many studies have been conducted to identify important edges in a graph, Grady et al. [6] pointed out that conventional methods typically rely on external or arbitrary parameters to extract meaningful structural features. In response, they introduced the salience of an edge for a graph and investigated the difference between edge-salience and edge-betweenness for a variety of networks from transportation, biology, sociology and economics. As a result, while the edge-betweenness distribution exhibited exponential trends, the edge-salience distribution displayed bimodality. The peak region containing edges with high-salience in the bimodal distribution allows us to easily identify important edges. Also, they provided the concept of high-salience skeleton (HSS) and demonstrated its effectiveness for various real networks. For example, the HSS effectively summarized global air traffic networks and successfully identified the infectious pathways in a social network for stochastic epidemic models. Due to its inherent potential, the HSS is expected to be applicable across a broader range of fields and challenges.

In this paper, we provide a novel problem of analyzing geographical road networks from a perspective of identifying critical streets for vehicular evacuation. When evacuating by vehicle during emergencies, the routes with the shortest distance are not always the most beneficial. Instead, there are cases where routes that offer easier traversal, even if they are longer, are more advantageous. Furthermore, evacuation destinations need not be restricted solely to conventional facilities or sites; wider and better maintained streets might also be viable options. Therefore, we focus on streets as basic units of road networks, and address the problem of identifying critical streets in a geographical road network, considering a scenario in which people efficiently move from specified starting intersections located around their residences to designated goal streets, following the routes of easiest traversal. In this paper, we first model a road network as a vertex-weighted graph obtained from its topological representation, where vertices and edges represent streets and intersections between them, respectively. The weight of each vertex reflects its ease of traversal. Next, we extend a recently introduced edge-centrality measure, salience, for our problem, and propose a method of detecting critical streets based on the vertex-weighted graph of topological representation by incorporating the notion of damping factor into it. We employ real-world road network obtained from OpenStreetMap, and experimentally investigate the characteristics of the proposed method by comparing it with several baselines.

2 Related Works

In recent years, there has been a growing interest in applying complex network science methods to geographical networks in the fields of geography, regional science, and urban science [4]. For instance, Monstis et al. [10] have statistically analyzed the relationship between commuting flows and the structure of a weighted railway network, where towns are represented as nodes and commuting flows are represented as weighted links. They examined the degree distribution as a centrality measure, demonstrating that they followed a power-law distribution. Furthermore, Porta et al. [11] conducted an analysis of the correlation between street-based networks and the density distribution of commercial and service activities in cities. They demonstrated a correlation between the global centrality metric Betweenness [5] of the street network and the distribution of human activities. Crucitti et al. [1] constructed road networks not only based on the conventional representation where intersections are treated as nodes and road segments between intersections as links, but also through a topological road representation where streets are considered as nodes and intersections as links, and analyzed the urban structures of various cities using four centrality measures, including Degree and Betweenness. They demonstrated that self-organized cities and planned cities exhibit different tendencies in terms of scale-free characteristics. However, to the best of our knowledge, there has been no study capturing road networks from the structural perspective of the HSS, as proposed by Grady et al. [6]. Incidentally, Ding et al. [2] have pointed out that although complex network science has contributed to research on urban transportation networks in recent years, there is a lack of comprehensive frameworks for integrating various methods. In this study, we introduce a method to integrate the HSS, which has typically been applied to conventional distance-based network representations, with a topological road representation focusing on the connectivity between streets rather than distance. Our approach uniquely tackles the previously unaddressed issue of identifying crucial streets in urban evacuation scenarios, setting it apart from prior research. It should be noted that, in road network data, there are instances where the attribute information defining a ‘street’ can be ambiguous. This presents a challenge in automatically determining the start and end points of a street from the data. While Jiang et al. [7] has tackled the challenge of constructing algorithms to extract natural streets, for simplicity, we consider the ‘Way’ elements from OpenStreetMap as ‘streets’ for our experiments.

Fig. 1.

Example of a geographical road network, an edge-weighted graph obtained from its geometric representation (GR), and a vertex-weighted graph obtained from its topological representation (TR).

On the other hand, research applying network science to evacuation route-related problems is also gaining attention. Do et al. [3] and Julianto et al. [8] have addressed the problem of route selection considering lanes in their analysis of evacuation routes assuming travel by car. However, these studies focus on addressing the local problem of choosing which lanes to take in a single road with multiple lanes. In contrast, our study is fundamentally different from them as it aims to extract critical streets for vehicular evacuation within a urban road network.

3 Preliminaries

We analyze a geographical road network within a city from an evacuation perspective (see Fig. 1). Here, the road network consists of streets $\{ S_m \}$ and intersections $\{ I_n \}$ (see Fig. 1a), and we assume that people move from specified starting intersections to designated goal streets. In Fig. 1a, two optimal routes from a starting intersection $I_1$ to a goal street $S_5$ are illustrated.

Conventionally, the road network is modeled as an edge-weighted graph $G_\textrm{g} = (V_\textrm{g}, E_\textrm{g}, W^{E_g})$ that is obtained from its geometric representation, where $V_\textrm{g}$ is the set of vertices corresponding to intersections, and $E_\textrm{g}$ is the set of edges corresponding to road segments that indicate the portions between two contiguous intersections along streets (see Figs. 1a and b). Also, $W^{E_\textrm{g}}$ is a weight function defined on $E_\textrm{g}$, and the weight of each edge indicates the real distance of its corresponding road segment (see Fig. 1b). Here, from the viewpoint of graph $G_\textrm{g}$, the shortest path from $I_1$ to $S_5$ in Fig. 1a is given by $\langle I_1, I_2, I_3, I_4 \rangle$ (see Figs. 1a and b). Note that this represents the route of the shortest distance.

On the other hand, the road network can also be modeled as a vertex-weighted graph $G = (V, E, W^V)$ that is obtained from its topological representation, where V is the set of vertices corresponding to streets, and E is the set of edges corresponding to those intersections at which two streets intersect (see Figs. 1a and c). When two streets intersect multiple intersections, we adopt one of such intersections as the edge between the two vertices (i.e., the two streets). Note that when more than two streets intersect at an intersection, the intersection can become multiple distinct edges in the graph G. Also, $W^V$ is a weight function defined on V, and the weight $W^V(S_m) > 0$ assigned to each vertex (i.e., each street) $S_m$ reflects its ease of traversal; smaller values of $W^V(S_m)$ indicate that the street $S_m$ is more easily passable. In the experiments, we set the reciprocal of the number of lanes in street $S_m$ as $W^V(S_m)$. Here, from the viewpoint of graph G, the shortest path from $I_1$ to $S_5$ in Fig. 1a is given by $\langle S_4, S_5 \rangle$ (see Figs. 1a and c). Note that this represents the route of the easiest traversal. In this paper, we focus on the graph G of the topological representation.

4 Detection Method

We begin by formalizing our road network analysis problem. Next, for our problem, we present a novel analysis method, which is naturally derived from the notion of HSS [6]. We also provide three alternative analysis methods for comparison purposes.

4.1 Problem Formulation

We consider the geographical road network within a specific city, $\mathcal{R}\mathcal{N}$, and focus on a situation in which people efficiently move from specified starting intersections to designated goal streets along optimal routes such as evacuation routes. For the road network $\mathcal{R}\mathcal{N}$, let $\mathcal{I} = \{ I_n \}$ and $\mathcal{S} = \{ S_m \}$ denote the sets of all intersections and streets, respectively. We fix the set of starting intersections, $\mathcal{I}^\textrm{start} \subset \mathcal{I}$, and the set of goal streets, $\mathcal{S}^\textrm{goal} \subset \mathcal{S}$. We can also consider the population $\rho (I_i)$ around each starting intersection $I_i \in \mathcal{I}^\textrm{start}$. Our final aim is to identify the critically important streets in the road network $\mathcal{R}\mathcal{N}$ in this situation.

In this paper, we utilize the vertex-weighted graph $G = (V, E, W^V)$ obtained from the topological representation of the road network $\mathcal{R}\mathcal{N}$. Let $E^\textrm{start} \subset E$ and $V^\textrm{goal} \subset V$ denote the counterparts of $\mathcal{I}^\textrm{start}$ and $\mathcal{S}^\textrm{goal}$, respectively. Then, our analysis problem is formulated as detecting the critical vertices in G under the population distribution $\rho (e_i)$ ($\forall e_i \in E^\textrm{start}$), considering the movement of people from $E^\textrm{start}$ to $V^\textrm{goal}$ along the shortest paths in G. Here, it is normalized that

$$ \sum _{e_i \in E^\textrm{start}} \rho (e_i) = 1. $$

4.2 Critical Vertices Detection Based on High-Salience Skeleton

For an edge-weighted graph, Grady et al. [6] introduced the notion of high-salience skeleton (HSS) by proposing the salience of each edge according the idea of identifying the average shortest-path tree from a reference vertex to the remaining vertices in the graph. We extend their work [6] for the case of our analysis problem. We introduce a new score $f(v_m)$ for each vertex $v_m \in V \setminus V^\textrm{goal}$, and use this score to detect the critical vertices in the graph G. We refer to this detection method as topological representation based HSS (TR-HSS).

Below, we provide the definition of the score $f(v_m)$ of a vertex $v_m \in V \setminus V^\textrm{goal}$ in TR-HSS. For each starting edge $e_i \in E^\textrm{start}$, let $v^+(e_i)$ and $v^-(e_i)$ denote the two vertices $e_i$ connects in G. For each $v_j \in V^\textrm{goal}$, we examine both the shortest paths from $v^+(e_i)$ and $v^-(e_i)$ to $v_j$, and select the shorter ones as the shortest paths from $e_i$ to $v_m$. Note that there can be multiple shortest paths from $e_i$ to $v_m$ in principle. In this way, we construct the shortest-path tree from $e_i$ to $V^\textrm{goal}$, represented as $T(e_i) = (T_1(e_i), \dots , T_M(e_i))$. Here, $M = |V|$ is the number of vertices in G (i.e., the number of streets in the road network $\mathcal{R}\mathcal{N}$), and each $T_m(e_i)$ is defined as follows: $T_m(e_i) = 1$ if vertex $v_m$ is part of at least one of the shortest paths from $e_i$ to $V^\textrm{goal}$, and $T_m(e_i) = 0$ if it is not. According to our analysis purpose, $T_j(e_i)$ is always set to 0 for all goal vertices $v_j \in V^\textrm{goal}$. Note that $T(e_i)$ indicates which vertices are included in the most efficient routes from $e_i$ to $V^\textrm{goal}$ for the graph G. Similar to the case of salience [6], we introduce the score $f(v_m)$ of each vertex $v_m$ in TR-HSS as

$$\begin{aligned} f(v_m) \ = \ C\sum _{e_i \in E^\textrm{start}} \rho (e_i) \, T_m (e_i), \end{aligned}$$

(1)

where C is the normalization constant ensuring that the maximum value of $f(v_m)$ is 1.

Next, we further enhance the TR-HSS by carefully examining whether the shortest paths from a starting edge $e_i \in E^\textrm{start}$ to a goal vertex $v_j \in V^\textrm{goal}$ include the shortest paths from $e_i$ to goal vertices other than $v_j$. We believe that this type of analysis is important since reaching the nearest safe locations is significant from the perspective of evacuation. To this end, we propose appropriately reducing the importance of vertices that appear after a goal vertex other than $v_j$ along the shortest paths from starting edge $e_i$ to goal vertex $v_j$. By introducing a damping factor p ($0 \le p \le 1$), we modify the definition of the shortest-path tree $T(e_i) = (T_1(e_i), \dots , T_M(e_i))$ from $e_i$ to $V^\textrm{goal}$ as follows:

• $T_m(e_i) = 1$ if there is a shortest path from $e_i$ to $V^\textrm{goal}$ that includes vertex $v_m$ and where a goal vertex does not appear before $v_m$.

• $T_m(e_i) = p^k$ ($1 \le k \in {\mathbb Z}$) if there is a shortest path from $e_i$ to $V^\textrm{goal}$ that includes vertex $v_m$ and where k goal vertices appear before $v_m$, but there are no shortest paths from $e_i$ to $V^\textrm{goal}$ that include $v_m$ and where $\ell$ goal vertices appear before $v_m$ ($0 \le \ell < k$).

• $T_m(e_i) = 0$ if $v_m$ is not included in any of the shortest paths from $e_i$ to $V^\textrm{goal}$.

Once again, we assume that $T_j(e_i) = 0$ for all goal vertices $v_j \in V^\textrm{goal}$. Then, based on the score $f(v_m)$ of vertex $v_m$ given by Eq. (1), the enhanced TR-HSS detects the critical vertices in G. Here, note that the enhanced TR-HSS with $p = 1$ is the same as the original TR-HSS.

4.3 Baseline Methods

To investigate the properties of TR-HSS in detail, we provide three baseline detection methods.

Rather than focusing on the shortest-path tree $T(e_i)$ from a starting edge $e_i \in E^\textrm{start}$ to all goal vertices $v_j \in V^\textrm{goal}$, we consider using the shortest-path list from $e_i$ to $V^\textrm{goal}$, represented as $L(e_i) = (L_1(e_i), \dots , L_M(e_i))$. Here, each $L_m(e_i)$ is the number of shortest paths from $e_i$ to $V^\textrm{goal}$ in which vertex $v_m$ is included. Then, we employ the score $f(v_m)$ of vertex $v_m$ that is obtained by substituting $L(e_i)$ to $T(e_i)$ in Eq. (1), and detect the critical vertices in G. This detection method can be equivalent to the traditional betweenness centrality, since unlike the case of graphs with homogeneous weights, shortest path between a given pair of vertices are typically unique in heterogeneous graphs with real-valued weights. Thus, we refer to the detection method as topological representation based betweenness (TR-BTW). In a similar fashion as TR-HSS, we enhance the TR-BTW by incorporating the damping factor p to reduce the significance of streets appearing after other goal streets.

For the conventional analysis of the road network $\mathcal{R}\mathcal{N}$, the edge-weighted graph $G_\textrm{g} = (V_\textrm{g}, E_\textrm{g}, W^{E_\textrm{g}})$, obtained from the geometric representation of $\mathcal{R}\mathcal{N}$, is often utilized. From naturally transforming the TR-HSS and TR-BTW for the graph G of topological representation into the graph $G_\textrm{g}$ of geometric representation, we can obtain two methods of detecting the critical road segments in the road network $\mathcal{R}\mathcal{N}$ (i.e., the critical edges in $G_\textrm{g}$). For our problem of detecting the critical streets in the road network $\mathcal{R}\mathcal{N}$, we leverage these two methods and identify those streets through finding the critical road segments included in them. We refer to the methods as geometric representation based HSS (GR-HSS) and geometric representation based betweenness (GR-BTW). Note that the GR-HSS and GR-BTW are regarded as straightforward applications of the conventional HSS and edge-betweennes centrality to our road network analysis problem, respectively.

5 Experiments

Using real road data from two cities, we experimentally evaluate the proposed TR-HSS with damping factor p by comparing it to the baseline methods TR-BTW, GR-HSS, and GR-BTW in terms of critical street detection. Furthermore, we give a detailed analysis of the critical streets detected by the TR-HSS with $p = 0$.

5.1 Datasets and Settings

We used OSM (OpenStreetMap) road data as the real road network data, and constructed two road network data, one for Kyoto City in Japan, which is characterized by a grid-like road network, and the other for Paris in France as an example of famous city. The road data in the target areas of Kyoto and Paris were extracted from the regions bounded by the latitudes and longitudes of the northwest and southeast corners. In OSM, each “Way” element consists of nodes corresponding to drawing points on the map and is stored as a road unit, which can include multiple intersections. For simplicity, we designated the “Way” elements as the streets and identified the intersections between Way elements based on their drawing points. However, there are instances where side roads or sidewalks run parallel to a street. We excluded such side roads and sidewalks. Furthermore, in the graph of GR, the edge weights of road segments were assigned to their actual distances calculated using the Hübeni formula based on the latitude and longitude information associated with the drawing point information in OSM’s Way elements. In the experiments, all intersections were specified as the starting intersections belonging to $\mathcal{I}^\textrm{start}$. As the goal streets belonging to $\mathcal{S}^\textrm{goal}$, we adopted the streets with four or more lanes. Note that $E^\textrm{start}$ $=$ E and $V^\textrm{goal}$ $\subsetneq$ V in the topological representation G $=$ $(V,E,W^V)$. The population distribution $\rho (I_i)$ ($I_i$ $\in$ $\mathcal{I}^\textrm{start}$) was assumed to be uniform. Table 1 summarizes the fundamental statistics of the datasets; the target areas, and the number of vertices, edges, and goal streets for both the geometric representation (GR) and topological representation (TR).

Table 1. Fundamental statistics of datasets

Fig. 2.

Distributions of street scores for the case of $V^\textrm{goal}$ $=$ V and of road segment scores for the case where the set of goals consists of all road segments.

Fig. 3.

Distribution of street scores for the TR-HSS and TR-BTW.

5.2 Results of Street Score Distribution

We first investigated the street score distribution for the case of $V^\textrm{goal}$ $=$ V and the road segment score distribution for the case where the set of goals consists of all road segments. Figure 2 shows the results of these distributions for two cities Kyoto (see Fig. 2a) and Paris (see Fig. 2b), where the street score distribution is displayed for the TR-HSS and TR-BTW, and the road segment score distribution is presented for the GR-HSS and GR-BTW. We see that both the street score distribution for the TR-HSS and the road segment score distribution for the GR-HSS are bimodal. Note that this kind of bimodal property for salience distribution is commonly observed in various real network data, as earlier mentioned in Sect. 1 (see [6]). On the other hand, we see that both the street score distribution for the TR-BTW and the road segment score distribution for the GR-BTW exhibit an exponentially decreasing nature. Note that this kind of property is typical for the betweenness distribution in real network data (see [6]). These results imply that the properties of salience and betweenness distributions also hold for geographical road networks, regardless of their topological and geometric representations.

We next investigate the effect of the damping factor p for the TR-HSS and TR-BTW for the two cities (see Fig. 3), where the streets designated as goals possess four or more lanes. As for the results of the TR-BTW (see Fig. 3a and b), the introduction of the damping factor p did not significantly alter the distribution trend. On the other hand, as shown in Fig. 3c and d, the bimodality for the TR-HSS with p $=$ 1 was still present, albeit less pronounced. However, when p became less than 1, the bimodal characteristics vanished rapidly, and the characteristics of the HSS distribution began to align with the trends observed in the betweenness distribution (see Fig. 3a and b). These trends yielded equivalent results for both Kyoto and Paris. However, even if the score distributions are similar, it does not necessarily mean that the detected streets are similar. Next, we will assess the overlap of critical streets identified by methods to be analyzed using the Jaccard index.

Fig. 4.

Comparison results of the TR-HSS with $p=0$ and that with other values of p ($p=0.25, 0.5, 1$) in terms of critical street detection.

Fig. 5.

Comparison results of the TR-HSS with p $=$ 0 and the baseline methods in terms of critical street detection.

5.3 Comparison Results of Critical Street Detection Methods

Using the Jaccard index, we measured how similar the critical streets detected by the TR-HSS with p $=$ 0 are to those detected by the TR-HSS with other values of p (see Fig. 4). As p increases, the difference in critical street detection between the TR-HSS with p $=$ 0 and that with other values of p grows. This suggests that the extracted critical streets are more dependent on the value of p as they rank higher. Moreover, the effect of p varies across cities. These results imply that the introduction of p is crucial for extracting critical streets.

Furthermore, using the Jaccard index, we measured how similar the critical streets detected by TR-HSS with p $=$ 0 are to those detected by each of the TR-BTW with p $=$ 0, GR-HSS, and GR-BTW. Here, the Basic stands for the GR-HSS in the case of $\mathcal{S}^\textrm{goal}$ $=$ $\mathcal{S}$. Figure 5 show the results. We can see that for the TR-HSS with p $=$ 0, there is almost no overlap with all baselines at top ranks. This suggests that the critical streets detected by the TR-HSS with p $=$ 0 are significantly distinct from those detected by the baseline methods.

Fig. 6.

Example of critical streets $S_1$, $S_2$, $S_3$, and $S_4$ detected by the TR-HSS with p $=$ 0 but not detected by the baseline methods.

Figure 6 displays a portion of the Kyoto City map. The city center of Kyoto is situated beyond the upper left of this map. A mountain in the middle of the map separates two regions of Kyoto City. The thick solid lines represent the goal streets with four or more lanes. Note that on the map, the “Goal Street” on the right side is a bypass with fewer access roads. The streets $S_1$, $S_2$, $S_3$, and $S_4$ are among the top 50 critical streets detected only by the TR-HSS with p $=$ 0. Note that $S_1$ is a tunnel that pierces through the mountain, $S_2$ is a road containing a junction between underground and surface, $S_3$ and $S_4$ are part of a connection road leading to a highway. By using narrower streets, we can identify several routes that connect the region on the right side of the map to the center of Kyoto City in a shorter distance than using street $S_1$. Note that there are many goal streets around the center of Kyoto City. It is known that the street $S_1$ is used as a detour route when heading from the area on the right to the goal in the upper left on the map. Here, we emphasize that our approach identified these critical streets that the baseline methods failed to detect. These results demonstrate the significance of our proposed method.

6 Conclusion

We provided a novel problem of analyzing geographical road networks from a perspective of identifying critical streets in the context of vehicular evacuation during disasters and emergency situations. In evacuation actions by vehicles, we posited that the shortest distance to the destination is not necessarily the optimal criterion. Additionally, the accessibility to the evacuation site is equally vital. Also, we considered that evacuation destinations don’t necessarily have to be conventional facilities or sites; wider and better maintained streets can also be relevant. Therefore, we focused on streets as basic units of road networks, and addressed the problem of finding critical streets in a geographical road network. Moreover, we considered a situation where people efficiently move from specified starting intersections to designated goal streets via the most accessible routes.

In this paper, we modeled a road network as a vertex-weighted graph obtained from its topological representation, where vertices and edges represent streets and intersections between them, respectively. The weight of each vertex reflects its accessibility. Then, we extended the edge-centrality measure, salience, and proposed a method of detecting critical streets based on the vertex-weighted graph of topological representation by incorporating the notion of damping factor into it. Using real-world road network obtained from OpenStreetMap, we experimentally revealed the characteristics of the proposed method by comparing it with several baselines. Our future work includes expanding our investigations to numerous other cities and further applying and enhancing our proposed method to address additional real-world challenges.