Introduction

Transportation systems possess a predominant role in the general movement to design smart, sustainable, and resilient cities (Cottrill and Derrible 2015; Derrible 2016a, b). Most cities around the world currently experience concerning growths in traffic flow. Traffic flow in city streets is directly related to both travel demand and the supply of roads. Travel demand notably originates from the need of residents to move to pursue activities, including work, shopping, medical, and leisure activities. Travel demand is often quantified by an Origin–Destination (OD) matrix, in which the element in the ith row and jth column shows the number of trips made from zone i to zone j. In contrast, the supply of roads consists of the physical infrastructure, including streets, alleys, and highways, and several studies have shown that the structure of an urban network has a substantial impact on its functional measures, e.g., speed, trip length, travel time, and traffic volume (Crane 1996; Tsekeris and Geroliminis 2013; Amini et al. 2016).

Adopting Network Science concepts, an increasing body of literature is now quantifying the supply of transportation based on network properties (Karduni et al. 2016). Specifically, urban networks are abstracted as graphs by taking intersections as nodes and roads as links (primal approach) or taking intersections as links and roads as nodes (dual approach). Space Syntax adopts a slightly different approach by considering entire streets as links (as opposed to street segments), and it has notably been applied to study network efficiency (Porta et al. 2006a, b; Mohammadzadeh and Rajabi 2013). Moreover, graphs that account for direction (i.e., one-way streets), as we do in this work are called directed networks, while graphs that do not are referred to as undirected networks, A fundamental problem in Network Science is to identify the most important nodes and links. For example, if we suppose a certain budget is to be assigned for network expansion, how does one determine the most suitable nodes/links for investment? The current state-of-the-practice focuses purely on travel demand, by giving priority to the most congested or most traveled streets and intersections. From a systems point of view, however, less traveled roads might be as important or even more important, for instance for resilience and emergency evacuation purposes.

The performance of an urban network depends on performance of its elements, i.e., roads and intersections. Poor performance may occur both as a result of gridlock caused by traffic congestion or by road closure due to infrastructure breakdown. In this article, we define the criticality of a link or node as the magnitude of the effect of its failure on the overall performance of the network. Here, the overall performance of the network is described in terms of its integrity and functional resilience. Integrity of the network is described through the relative size of the giant component, and functional resilience is described through the value of a network’s adaptive capacity (a technical definition is given in the methodology section).

In this study, we analyze the correlation among centrality, criticality, and the flow passing through nodes and links in a real urban road network. The rationale is that if two variables are highly correlated, one of the two can be used as a “surrogate” of the other, which can help plan and assess future projects. For instance, enhancing the capacity of nodes with higher flows, would not only improve their throughput, it would also improve network resilience in general. Many measures exist to evaluate the importance of nodes in a network. Degree centrality, betweenness centrality, and closeness centrality are among some of the most common measures of node importance (Gao et al. 2013). Eigenvector centrality (Bonacich and Lloyd 2001), Katz’s centrality (Katz 1953), Leader Rank centrality (Lü et al. 2011) and PageRank (Brin and Page 2012) capture both the number and the influence of a node’s neighbors (Wu et al. 2016). Several studies have combined various measures to determine the importance of nodes (Xinsheng et al. 2011; Hu and Liu 2015). Furthermore, Liu et al. (2016) proposed a measure of node importance based on degree and importance of lines (DIL); they showed that compared to local centralities, DIL more effectively captures the importance of bridge nodes, i.e., nodes connecting two important nodes. Wang et al. (2010) developed a measure based on the degree of the node and the degree of its neighbors. Ren et al. (2013) developed a measure by combining degree and clustering coefficient. Morone and Makse (2015) considered the degree of the target node and its neighbors that are a certain number of steps away from it to develop collective influence (CI) of the nodes. Wu et al. (2016) modified CI and developed enhanced collective influence (ECI) by considering loop density and the diversity of node degree. From a different perspective, Kermanshah and Derrible (2016a, b) capture resilience using multiple criteria, both from travel demand and network topology. An excellent collection of node importance measures can be found in Lü et al. (2016) and Wang et al. (2017). Gao et al. (2013) used taxi trajectory data of Qingdao (China) to evaluate the capability of the betweenness centrality of the urban network to predict traffic flow and concluded that betweenness centrality measure is not a suitable predictor for actual flow. Crucitti et al. (2006) studied distributions of five centrality measures over geographic networks of eighteen 1-square-mile samples of different world cities urban streets. They concluded that despite the diversity of the studied cities, closeness, straightness and betweenness followed statistically similar distributions in all cases. Information centrality distribution was found to be exponential in planned cities and power-law in self-organized cities.

The main objective of this article is to investigate the correlation among the centrality, criticality and flow passing through nodes and links of an urban street system. Specifically, we aim to:

  • Identify the most critical nodes and links of an urban street network; i.e., nodes and links that must be given the highest priority in order to enhance the resilience of the network.

  • Calculate the correlation between the flow and centrality of nodes in an urban street network.

  • Determine the correlation between the flow and the criticality of nodes in an urban street network.

In the next section, we describe the research method. As a case study, we then apply the method to the road network of Isfahan (Iran) and we discuss the results.

Methodology

Centrality analysis

Betweenness centrality (BC) is often recognized as a preferred measure of centrality. It focuses on the importance of a node/link to be used in a path to link two nodes as opposed to focusing on its closeness to other nodes. More specifically, betweenness centrality measures the extent to which a node lies on the shortest paths between any pair of nodes (Newman 2010). The betweenness centrality of node i (CB(i)) is formulated as:

$$C_{B} \left( i \right) = \frac{{g_{jk} \left( i \right)}}{{g_{jk} }}$$
(1)

where gjk is the number of shortest paths between nodes j and k, and gjk(i) is the number of those shortest paths that go through node i (Opsahl et al. 2010). A path is a sequence of nodes connecting an origin node to a destination node without passing any node more than once. In large networks, pairs of node can usually be connected by multiple shortest paths, where a shortest path is a path that connects a pair of nodes by passing the minimum number of links. In case of weighted networks, a shortest path is a path that has the minimum sum of link weights.

The relevance of betweenness centrality for transportation is trivial since it is conceptually close to traffic volume. Moreover, since betweenness centrality is based on shortest paths, it can take into account link weights; e.g., travel time, distance, or a generalized cost. In this research, we calculate six different betweenness centralities: no weight (i.e., the traditional BC that essentially assigns a weight of 1 to all links), traffic flow, link length, travel time (simulated), congestion (ratio of traffic volume to link capacity), and the reciprocal of link capacity (i.e., capacity−1). The reason to use the reciprocal of link capacity is that intuitively, due to higher speed limits, roads with higher capacity are more easily traversed than those with low capacity.

Subsequently, we analyze the correlation among node centralities and intersection traffic flow. Trip assignment was carried out within a user-equilibrium framework. The trip assignment results were then validated by comparing the observed flows on the selected links with the outcomes of the assignment during morning peak hours.

Sensitivity and criticality analysis

The sensitivity of a network is the extent to which the network is affected by a disturbance (Gallopín 2006). It can be measured as the amount of degradation in network functions per unit of change in the disturbance (Tomović 1963). The amount of change in the performance of a network can be quantified by various methods, including by the change in the size of the giant component (Callaway et al. 2000; Osei-Asamoah and Lownes 2014), network adaptive capacity (Yoo and Yeo 2016), by network efficiency (Dunn and Wilkinson 2016), by the total amount of travel time throughout the network (Scott et al. 2006), by the network equivalent resistance (Ellens et al. 2011), and by the network diameter (Albert et al. 2000). In this article, the relative size of the giant component and the network adaptive capacity were adopted as the measures of sensitivity. Both concepts are defined below.

Giant component

The giant component of a network is the largest set of connected nodes of the network. The size of the giant component is therefore the number of nodes in the giant component, and the relative size of the giant component is the ratio of the size of the giant component to the size of the network. Removing particularly important nodes may cause some other nodes to lose their connection with the rest of the network. The number of these isolated nodes is therefore subtracted from the size of the network to yield the size of the giant component. Values close to 1 for the relative size of giant component close indicate that the network is well connected.

Adaptive capacity

The adaptive capacity of a network is the amount of extra flow it can handle. Adaptive capacity quantifies the ability of a network to replace an attacked node with its adjacent nodes. Each node of a network has a capacity that is represented by the hourly throughput the node is able to sustain.

In urban road networks, a missing node is not necessarily compensated by its adjacent nodes. This is because travelers try to find the shortest path connecting their origin to their destination, and when a node is removed, a completely different path may be selected. Therefore, we have applied adaptive capacity as a measure of the network redundancy; i.e., it is equal to the difference of the sum of node capacities and the number of trips passing through all nodes.

Node flow is the number of particles (vehicles in this case) passing through it. The ratio of node flow over capacity is traditionally seen as a measure of congestion. Finally, the margin of a node is the difference between its capacity and its flow; i.e., the amount of extra flow it can handle. When a node is removed from a network, its flow is redistributed to other nodes of the network. If the sum of the margin of the other nodes is greater than the flow of the targeted node, they will be able to handle the flow of the removed node. In this case, we say that the network is resilient to this particular event. As the number of removed nodes increases, the network margin decreases and finally the flow of removed nodes exceeds the network’s margin, leading to network failure.

Figure 1 illustrates this concept. Assume node number 3 in the network were removed, its flow would be redistributed to its adjacent nodes 1, 2, 4, and 5. In Fig. 1a the flow of the removed node is 80, and the margins of its neighbors are 80. The flow of the removed node can therefore be redistributed to other nodes and the network will continue to perform. In Fig. 1b, however, because the flow of the removed node (100) exceeds the margins of its neighbors, the additional flow cannot be handled, and the network will collapse.

Fig. 1
figure 1

An example for calculating adaptive capacity

Full size image

We define the adaptive capacity of a network as the ratio of remaining margins to initial margins of the network as:

$$A = \frac{{\sum\nolimits_{i}^{n} {m_{i} \left( k \right) } }}{{\sum\nolimits_{i}^{n} {m_{i} } }}$$
(2)

where n is the size of the network (number of nodes), mi is the margin of node i, and mi(k) is the margin of node i after node k is removed (Yoo and Yeo 2016).

The results of the analysis are described in the next section.

Perturbation strategy

To test the resilience of the network, perturbations were imposed by removing the nodes and links of the network. Specifically, the nodes are removed one by one, and when a node is removed, all of its incident links were removed as well. When a link is removed, however, its nodes were maintained and counted in the network size. The number of removed links and nodes throughout the network show the magnitude of the perturbation. Perturbations are enforced cumulatively; i.e., at each removal step, the set of removed nodes gets larger and larger.

The order to which the nodes and links are removed affects the performance of the network (Wang et al. 2017). Therefore, nodes were sequentially removed from the network and the size of the giant component and adaptive capacity were calculated at each step. We used four strategies of node and link removal (each time from the highest value to the lowest value): (1) node degree, (2) betweenness centrality, (3) strength (sum of the capacity of incident links), and (4) traffic flow. The ordering that yields the fastest drop in the relative size of the giant component and the adaptive capacity is hypothesized to better capture node criticality.

Case study and results

The method described in the previous section was carried out on the urban street system of Isfahan in Iran. Isfahan is the third largest city of Iran, and it is located in the central part of the country with a population of 1.7 million. The urban street system of Isfahan consists of 2150 nodes and 4760 links.

Node betweenness centralities were first calculated with the six different types of weights defined in “Methodology” section: (1) 1 (i.e., no weights), (2) traffic flow, (3) link length, (4) reciprocal capacity, (5) congestion, and (6) time. Figure 2 shows particularly well that the values of betweenness centrality depend heavily of the type of link weights selected; in Fig. 2, darker colors and larger circles indicate higher centrality values. For example, with reciprocal of capacity as link weights, we can see that nodes located on the belt highway of the city have the highest betweenness centralities (Fig. 2d), whereas with length as the link weights, the nodes located in the central part of the city have the highest betweenness centralities (Fig. 2c). Surprisingly, with congestion as link weights, peripheral and relatively low-volume links have the highest betweenness centralities (Fig. 2e).

Fig. 2
figure 2

Betweenness Centralities of Nodes. Darker and larger circles have higher betweenness centralities. a weight = 1, b weight = flow, c weight = length, d weight = capacity−1, e weight = congestion, f weight = time

Full size image

The Pearson correlation coefficients between the six types of node betweenness centrality are shown in Table 1. From the table, we can see that time and reciprocal capacity are significantly correlated with a Pearson coefficient of 0.89. Betweenness centrality with no weight is also correlated with reciprocal capacity (0.69) and time (0.64), although to a lesser extent.

Table 1 Correlation among values of node betweenness centrality
Full size table

The Pearson correlation coefficients between the six types of link betweenness centralities are shown in Table 2. From the table, we can see that none of these betweenness centralities are significantly correlated.

Table 2 Correlation among values of link betweenness centrality
Full size table

The correlation among node flows (i.e., total traffic volume entering a node) and betweenness centralities were also calculated and are presented in Table 3. In particular, we can see that traffic flow and reciprocal capacity are statistically correlated with a Pearson coefficient of 0.66.

Table 3 Correlation among node flows and their centrality measures
Full size table

Finally, since flow is arguably more relevant to link attributes (as opposed to nodes), values of link betweenness centrality were calculated and analyzed. Table 4 shows the values of correlation among flow, capacity, betweenness centrality (i.e., link BC), and congestion (ratio of flow to capacity). The table shows high correlation between flow and link capacity, which is expected since the two are essentially measuring the same thing. It also indicates that link BC and congestion are not correlated in the network under study. Figure 3 shows the links with highest values of link betweenness centrality in the network. In this figure, thicker links represent higher link betweenness centralities.

Table 4 Correlation among attributes of links
Full size table
Fig. 3
figure 3

Betweenness of the links of the network

Full size image

From Table 4, we can also see that betweenness centrality and flow seem to be mildly correlated with a Pearson coefficient of 0.59. To further explore the relationship, Fig. 4 shows link normalized betweenness versus normalized flow. These scatterplots do not suggest any specific patterns but conform to the intuition that the betweenness centrality of a link is less than the betweenness centrality of its tail and head nodes.

Fig. 4
figure 4

Scatterplot of link flows versus link betweenness

Full size image

Node criticality

The second part of the research investigates the correlation between nodes’ centrality and flow under node and link removal. Figure 5 shows the breakdown behavior of the network as the result of the node removal process by targeting nodes with higher betweenness centralities first. At each step, one hundred nodes were removed, which is about 5% of the total number of nodes.

Fig. 5
figure 5

Normalized link betweennesses versus the normalized betweenness of their source and target nodes

Full size image

From Fig. 6, we can see that the network remains relatively stable for removals less than 20%, regardless of the weight type for betweenness centrality. After 20%, however, the relative size of the giant component rapidly decreases, and the network collapses when around 50% of the node are removed, again regardless of the weight type. Moreover, the slope for BC(1) (i.e., no weight) is steeper than all others, which suggests that removing nodes with higher BC(1) values has a larger impact.

Fig. 6
figure 6

Comparing the effects of betweenness centrality

Full size image

Figures 7 and 8 show the effect of node removal on the relative size of the giant component and the adaptive capacity of the network, by targeting nodes using the perturbation strategy presented above. Figure 7 shows that for node removals smaller than 15%, node strength better captures criticality in terms of impact on the connectivity of the network. For node removals larger than 20%, both strength and BC(1) show the highest impacts.

Fig. 7
figure 7

Comparing the effect of node removal on the relative size of the giant component

Full size image
Fig. 8
figure 8

Comparing the effect of node removal on adaptive capacity

Full size image

Figure 8 shows the impact of targeted node removal on adaptive capacity. We can see that unlike the other node removal plots, adaptive capacity has a linear behavior as nodes are being removed. This linear behavior is due to the fact that the adaptive capacity of a network is a linear function of the sum of its link capacities. As importantly, we can see that the network starts to collapse when about 15% for strength, 18% for flow, and 23% for betweenness and degree of the nodes are removed, which is substantially lower than the two previous figures. These results particularly emphasize the need to preserve the capacity of the links connected to nodes with higher strengths since their failure would have the most negative impacts on the adaptive capacity of the network.

Link criticalities

A similar perturbation strategy was carried out for road links. The link measures collected are capacity, flow, and congestion. Values of betweenness centralities were also calculated. From Fig. 9, we observe that for capacity, significant impacts start to appear when about 15% of the links are removed. This number increases to 25% for flow and betweenness, and to 40% for congestion. These results suggest that for perturbations that affect up to 30% of urban nodes, the network is most vulnerable to losing its high capacity nodes. For perturbations affecting more than 30% of urban nodes, network is most vulnerable to losing nodes with highest betweenness values. Interestingly, losing nodes with highest congestion is the least vulnerable alternative.

Fig. 9
figure 9

Comparing the effect of link removal on the relative size of the giant component

Full size image

Conclusion

In this article, we investigated the correlation between traffic flow, node centrality, and node criticality. Overall, we found that travel time and reciprocal of capacity yielded similar betweenness centrality results when used to weight links. In addition, these two measures were relatively highly correlated with node flow. These results suggest that network topology has a relatively significant effect on traffic flow. Moreover, among the various weight types, traditional betweenness centrality (i.e., no weight) best captured essential element of urban street system resilience. In terms of node criticality, node strength (i.e., weighted degree based on capacity of the incident links) showed a more significant impact, however. Furthermore, capacity was best able to capture link criticality when less than 30% were removed. Beyond 30%, both betweenness centrality captured link criticality.

The results of this study can generally be applied in urban street network planning and traffic management. For instance, when planning to improve the resilience of an urban street system, emphasis should be put into ensuring that nodes with high capacity and betweenness are able to operate properly or are supplemented with new infrastructure. Congested links and nodes were not found to be as significant. For the specific case of Isfahan, nodes with the highest values of degree (circle), capacity (square), flow (diamond), and betweenness (triangle) are shown in Fig. 10. From the figure, we can see no overlap between the nodes highlighted. These results clearly demonstrate that multiple measures should be used in the decision-making process to selection the location of future projects.

Fig. 10
figure 10

Nodes with highest values of betweenness, capacity, and congestion

Full size image

Overall, as cities across the world are trying to adapt to growing congestion, new models and new tools and techniques are now emerging in the literature that can provide relevant information about the performance of a system (Derrible et al. 2010; Derrible and Ahmad 2015; Ahmad et al. 2016). This study looked at travel demand and network centrality characteristics, but much work lies ahead for cities to become smart, sustainable, and resilient.