I Introduction
Cities evolved, and continue evolving, into different organizational patterns as a consequence of historical, political, financial and efficiency circumstances Bettencourt and West (2010); Batty (2012). Similar to the manybody problem, city constituents usually interact with one another, requiring a complex systems perspective to describe the observed phenomena. Urban transportation networks, on top of road networks, are a paradigmatic example of such scenarios.
The analysis of these systems has taken different approaches depending on their scale and purpose. Dynamics on interurban roads (a.k.a. arterial roads, or high capacity roads), characterized by long segments and limited interconnection, is governed by the interaction between cars circulating within. Thus, most of the phenomena can be explained by considering vehicles moving on independent roads, e.g., using carfollowing models and fluid dynamics Helbing (2015), or the macroscopic fundamental diagram Godfrey (1969); Daganzo and Geroliminis (2008). On the contrary, dynamics on intraurban roads, characterized by short street segments with frequent interactions between them, is basically driven by road intercommunication, where vehicles can relocate to different segments during their trajectory. In these situations, complex networks theory plays a salient role. Theoretical models developed along these lines have helped to understand the observed phenomena on such systems, e.g., urban mobility Barthelemy and Flammini (2009); Balcan et al. (2009), traffic Guimerà et al. (2002); Echenique et al. (2005); Ling et al. (2010); SoléRibalta et al. (2018); Akbarzadeh and Estrada (2018); Verbavatz and Barthelemy (2019); Gao et al. (2019); Chen et al. (2020), road usage Wang et al. (2012); Strano et al. (2012), and network collapse Olmos et al. (2018); Zhang et al. (2019); Zeng et al. (2019).
These, a priori independent, transportation networks are increasingly entangled as cities sprawl over suburban areas. Under a multilevel analysis, these systems may develop special phenomena SoléRibalta et al. (2016). Up to date, only few works have studied the urban transportation networks from this intertwined (and entangled) perspective, and their implications have been barely analyzed. In Kirkley et al. (2018) the authors describe the structural properties of systems where arterial and local urban roads share the same geographic space Wegman and Aarts (2006). This model allows them to explain the shape of the experimentally observed universal betweenness distribution of the road networks of 97 cities worldwide.
In this work, we consider the complementary situation in which arterial roads and urban local ones operate on separate geographic spaces. Specifically, local roads are basically located at the city center, and arterial roads at the urban periphery. This model, that we call GridTree model or GTmodel, reproduces previous results in terms of betweenness distribution Kirkley et al. (2018), and provides a different, yet plausible, explanation for them.
A considerable advantage of the GTmodel comes from its analytical tractability. GTmodel equations evidence that cities may experience a set of multiple abrupt phase transitions in the spatial localization of congested areas. These transitions define a set of congestion regimes, that we also empirically find in many cities worldwide. These regimes imply the emergence of congestion in the city center, its periphery or in urban arterial roads, and are related to the way different road types are entangled to form a unique road transportation system.
The manuscript is organized as follows. In Sec. II, we discuss the importance of the betweenness centrality in urban settings, its characteristics when the network is embedded in Euclidean spaces, and we relate our work with the recent literature. In Sec. III, we develop our GTmodel and analyze it in terms of known results related to the betweenness distribution and its spatial behavior. Section IV is devoted to the derivation, and subsequent validation, of the analytical expressions for the betweenness of several crucial nodes of the GTmodel. In Sec. V we derive, using the previous analytical calculations, the abrupt transitions which define the congestion regimes. The existence of these different congestion regimes is validated with empirical road networks associated to real cities in Sec. VI. Finally, Sec. VII contains some concluding remarks and perspectives.
Ii Betweenness distribution in cities
Betweenness, initially introduced in social sciences Freeman (1977, 1978), is a centrality measure of network constituents (nodes and edges) which quantifies their importance, in terms of the amount of paths crossing them. Besides sociology Goh et al. (2003); Everett and Borgatti (2005); Leydesdorff (2007); Kourtellis et al. (2013); De Arruda et al. (2014, 2014), betweenness centrality has been used in several other problems of interest: community detection Girvan and Newman (2002); Newman and Girvan (2004), epidemic spreading Matamalas et al. (2018), percolation Xia et al. (2010); Wandelt et al. (2018), and targeted attacks to networks Holme et al. (2002); Wang and Rong (2009); Iyer et al. (2013); Bellingeri et al. (2014), to name a few Barthelemy (2004); SoléRibalta et al. (2014); Wang et al. (2015); De Domenico et al. (2015)
. Yet probably one of the most prominent applications is in the analysis of traffic and routing
Guimerà et al. (2002); Echenique et al. (2005); Zhao et al. (2005); Yan et al. (2006); Liu et al. (2007); Dolev et al. (2010); Dong et al. (2012); Tan et al. (2014); SoléRibalta et al. (2016, 2016, 2018); Manfredi et al. (2018); SoléRibalta et al. (2019). Betweenness centrality is implicitly related to the concept of path which, in turn, depends on the routes that elements take while traversing the network. Several definitions of betweenness have been proposed to account for the specific routing dynamics of the elements Newman (2005); Estrada et al. (2012).We focus on the classical definition based on shortest paths routing dynamics (in time or length) over urban roads networks. Recent studies indicate that drivers (and pedestrians) may opt for alternative trajectories larger than the shortest path Quercia et al. (2014), but the assumption of shortest path dynamics is still a crucial routing model, based on the rational choice of trajectories, thus helping in the design and analysis of transportation networks. In this context, the shortestpaths betweenness () considers only geodesic paths between city locations and is defined, for a given node , as:
(1) 
where is the number of shortestpaths going from origin to destination , while is the number of these paths crossing . Factor , usually taken to be , , (where represents the number of nodes in the network), or even 1, represents a normalization constant which may be different depending on the application. For convenience, we will calculate the unnormalized betweenness, setting .
As already evidenced by Guimerà et al. Guimerà et al. (2002), the analysis of the betweenness distribution is crucial for understanding the dynamical properties of transportation networks since it is an accurate proxy of node and link usage, which combined with other properties (e.g., processing capacity) can accurately predict congestion. Recently, Kirkley et al. Kirkley et al. (2018) have shown that, when networks are attributed with planar properties, such as urban road networks, these distributions display a similar shape that scales with . Additionally, there is a strong dependence between node betweenness and its geographic position. In general, low betweenness nodes are located at peripheral regions, while high betweenness nodes appear near the urban center. This distribution can be seen in Fig. 2 for three different cities (see Fig. 2 of Kirkley et al. (2018) for a large scale analysis). The right hand side of the betweenness distribution can be approximated with a powerlaw with an exponential cutoff: . Exponent happens to be quite stable, with values . However, the value of has a strong dependence on the size of the city Kirkley et al. (2018).
Iii Gridtree model for city road networks
The shape of the tail of the betweenness distribution suggests that there might be a structural transition between different network topologies as we depart from the city center. At large distances, we mainly expect to find arterial roads, whose connectivity may resemble a tree. The betweenness distribution of trees follow a powerlaw which is compatible with low influence on the cutoff parameter on . As distances approach the city center, the presence of local roads increases and the structure of the network increments in regularity. Although many types of regular networks could mimic this structure, e.g. Delaunay triangulation or rectangular grids, most of them have equivalent properties in terms of betweenness. These structures provide high interconnectivity between city center buildings, with high redundancy of paths, offering, in turn, higher resilience to congestion than treelike structures. A grid graph displays a betweenness distribution with a significant cutoff.
These observations allow us to set the basis of our model for road networks, composed of a rectangular grid to describe the city center, connected to trees that model the periphery. More precisely, our gridtree model (simply GTmodel hereafter) consists of a regular grid, of size , connected with a set of trees with height and branching factor , see Fig. 1. We suppose the trees are full and complete.
The number of nodes of the grid, , and of the trees, , are given by
(2) 
while the size of the GTmodel structure is
(3) 
For simplicity and symmetry of the GTmodel, we choose four trees (
), an odd number for the sides of the grid (
, with ), and assume that trees are connected to the central node of each side, see Fig. 1.Compared to actual cities of diverse size, the GTmodel reproduces the range (right branch) of the betweenness distribution in Fig. 2 (red line in panels ac). These are the nodes with larger betweenness centrality, the critical ones to many network phenomena. This is a clear evidence that this simple regular network model may suffice for the analysis of these phenomena. The left hand side of the rescaled betweenness distribution, range , corresponding to low values, emerges with the addition of structural noise to the GTmodel. We have tested three types of noise: random addition and removal of edges (both with distance bias), and Delaunay noise. See Appendix A for a detailed description of noise generation procedures.
QQplots for the three cities in Fig. 2 show that the GTmodel leads to similar shapes of the betweenness distribution, and specially, a good fit for the upper part of the distribution. The lower part of the distribution, corresponding to the structural noise, slightly underestimate betweenness.
Additionally, as important as the shape of the distribution, is the relationship between the node’s geographic position and its betweenness. We show in Fig. 3 and Supplemental Fig. S3 that the GTmodel recovers the monotonic decrease of the larger betweenness nodes, as well as the average betweenness, as we move away from the city center. Furthermore, it not only recovers the general trend but also the deviation of these values, i.e., large deviations for nodes near the city center, and low deviations for peripheral regions.
These positive results depend, of course, on the choice of the parameters. The accuracy of the GTmodel is determined by the values taken by , , , and the level of noise. In particular, it is governed by the ratio between and . As this ratio grows, the highbetweenness distribution branch approaches the form of a grid and the cutoff has an influential role, while in the opposite case a powerlaw emerges as it is related to the betweenness distribution of the tree. Results in Fig. 3 correspond to intermediate regimes.
Iv Analytical derivation of betweenness in the GTmodel
For a large set of traffic models and strategies, the critical injection rate of vehicles, , i.e., the maximum rate at which vehicles can enter the system without congesting it, can be obtained in terms of the maximum node betweenness, Guimerà et al. (2002); Zhao et al. (2005); Echenique et al. (2005); Yan et al. (2006); Liu et al. (2007); Dong et al. (2012); Tan et al. (2014); SoléRibalta et al. (2016); Manfredi et al. (2018):
(4) 
The value of sets the onset of congestion. Thus, it makes sense to study routing dynamics over the GTmodel in such terms. Here, we are interested in understanding how topological changes in terms of the GTmodel model parameters (i.e., , and ), affect the position of in the network.
Numerical exploration of the (noiseless) GTmodel reveals that the onset of congestion is set by nodes located at three different key network positions: the center node of the grid (red node in Fig. 1), at connector nodes on the perimeter of the grid (nodes with a circumscribed circle), or at the root of the trees (nodes with a star within). We will refer to these nodes as gridcenter (gc), connector (c), and treeroot (t), respectively. According to them, it is possible to define three different congestion regimes, which correspond to the location of the node that marks the onset of congestion. Therefore, the transportation network may collapse in the city center, in the perimetral city roads (ring roads), or in arterial roads. Note that in these two last cases, because of symmetry, we have four nodes with equivalent structural properties (see Fig. 1).
According to Eq. (4), the understanding of which circumstances lead to each regime, goes through the analysis of the betweenness for these three types of nodes. The rest of this section develops the analytical expressions of the betweenness for these nodes of interest, while we leave for the next Sec. V the analysis of the congestion regimes. To this aim, we proceed in the classical way of counting the number of paths crossing each of the nodes, according the definition in Eq. (1). As we will see, regularities in the network allow for an efficient computation of such values. For the sake of simplicity, we assume that origin and destination nodes do not contribute to the betweenness of such nodes. Otherwise, one should add to each node: for the paths where the node is origin, and for the paths where the node is destination.
Considering the structural composition of the GTmodel, each node may be traversed by three different types of paths: (1) paths with origin and destination in the trees; (2) paths between a tree and the grid; (3) paths within the grid. The betweenness of each node can be obtained as the sum of the contributions of each of these types of paths. Specifically, the betweenness of any node in the network can be written as a seconddegree polynomial:
(5) 
with different coefficients depending on the GTmodel parameters. The constant term considers the contribution of paths fully contained within the grid, which does not depend on the parameters of the tree. The linear term , instead, considers the contribution of paths that go between a tree and the grid, while the first term, , considers the contribution of paths that go between trees. All the coefficients , , and depend on the grid parameter ( or ), and for the treeroot node, also on .
The analytical computation of the coefficients of is cumbersome. Consequently, to improve readability of the paper, in the following, we only describe the mechanism we use to obtain the betweenness for the gridcenter node (), and postpone the derivation of the betweenness for the connector node () and the treeroot node () to Appendices B and C, respectively.
Coefficient of the betweenness of the gridcenter node can be expressed as:
(6) 
where corresponds to the distance between the central node of the grid and its sides, see Fig. 1, and we have defined , the number of different paths in the grid involving horizontal and vertical steps:
(7) 
As described in Eq. (5), only considers the contribution to betweenness of paths with origin and destination belonging to nodes in different trees. Following Fig. 1, which visually describes the process, we first consider the betweenness contribution to the gridcenter node (colored in red) of paths that go from to . Each of these paths contributes with a unity to , since all paths between those nodes go though the central node. Since we could also choose the paths between and , we obtain the in Eq. (6).
Now consider the contribution of paths that go from either or to nodes within . All these paths are canalized through nodes and , and there are many paths of equal length between and : we have path multiplicity (or degeneration). Some of them are illustrated in green lines in Fig. 1. We proceed combinatorially to count all these paths. Consider we need to move steps to the right () and steps down () to go from to . There are ways in which we could order the and operations. Only one of these paths goes through the central node, the one where all operation precede the ones. In this way, the betweenness contribution of any of the paths that go from nodes in or to nodes within is . Considering there are four different origindestination combinations in this configuration —(), (), () and ()— we add a factor 4 to Eq. (6). Note that we do not have to account for the reversed assignment of the trees as origin and destination, e.g., (), due to the reversibility of the paths; if we calculate all the shortest paths from node to node , it is not necessary to do the same for paths between and .
The expression for is the following:
(8) 
Figure 1 provides a visual support for the explanation of the terms in Eq. (8). Consider a node identified with variables , i.e., located at horizontal and vertical steps of the central node of the grid. The shortest paths whose destination node is within tree and that go through the central node, are paths whose origin is located on the lefthand side of the grid, shaded in orange in the diagram. Any of these origindestination pairs has different paths that cross the central node, and paths to reach the connector node that connects the grid and the tree, since the connector node is nodes to the right of the central node. Thus, each of the origindestination pairs contribute to the betweenness of the central node with a factor .
We can now exploit the grid’s symmetries to obtain their total contribution to the betweenness of the central node. For each origin node above the central node there is an equivalent node below it, thus a factor 2 must be added. However, for nodes with , there is just one path to the destination, and it crosses the central node, thus the term in front of the sums. Finally, a factor 4 to both terms is necessary to account for the 4 possible destination trees connected to the grid, thus completing all the terms in Eq. (8).
The calculation of coefficient is similar to the previous ones, with just the difference that both origin and destination of the paths belong to the grid. The result is
(9) 
The idea is to consider that the origin node is identified with variables and the destination node with , where and represent the horizontal distances to the grid center, while and are the corresponding vertical distances. There exist four different configurations for the relative positions of these origin and destination nodes, that lead to the four terms in Eq. (9).
In the first term, the origin and destination are aligned with the grid center, i.e., for a vertical alignment, and for the horizontal alignment. They amount a total of nondegenerated shortest paths per alignment, in which all of them contain the gridcenter node.
The second term considers the cases in which origin and destination nodes are, one aligned horizontally and the other vertically with the grid center, i.e., the cases and . There are four of these combinations, and in all of them there is only one shortest path that crosses the grid center. If we choose for example the case , there exist a total of shortest paths between the origin and the destination, thus explaining this term in Eq. (9).
Next, we have the situation in which the alignment with the grid center is limited to one of the nodes, and in one of the directions; let us choose the destination node and the horizontal alignment, i.e., . Now, only of the shortest paths connecting origin and destination pass through the grid center. Since there are eight possible origindestination configurations with this relative alignment, they explain the third term in the r.h.s. of Eq. (9).
Finally, the last term comes from the two configurations where no alignment is present, with shortest paths crossing the grid center among the connecting origin and destination.
Once we have computed the three coefficients, the betweenness of the grid center is simply:
(10) 
Note that the same approach could have been used to obtain the betweenness of all the nodes in the grid, not just the grid center. Basically, the limits of the sums in Eqs. (8) and (9) would change to reflect the new position of the reference node, some terms would disappear from the coefficients due to the node not being within a shortest path, and special care would be needed to account for nodes in the sides and corners of the grid. The analysis for one type of these nodes, the connector node, is available in Appendix B, while in Appendix C we show the calculation of the betweenness for all of the nodes in the trees, including the important treeroot node.
V Congestion Regimes
The position of the maximum betweenness node provides information about which city areas determine the collapse of the transportation network. The three regimes (central’s grid, connector and treeroot node) we have discussed in the previous sections may be interpreted as different congestion phases which characterize a urban system. In this section, we establish a relation between the three congestion regimes and the parameters of the GTmodel. Precisely, given the values of , and , we conclude where, geographically, congestion occurs.
The transition between two different regions is defined by the condition
(11) 
where and are two distinct regimes. For instance, the frontier between the treeroot () and the connector node () regimes is defined by the equation
(12) 
with and introduced in Eq. (5). Clearly, Eq. (12) is a seconddegree polynomial:
(13) 
with
(14)  
(15)  
(16) 
Then, by using the equations in Sec. IV, and Appendices B and C, we can provide an analytic solution to Eq. (13):
(17) 
with the discriminant
(18) 
In a similar way we can obtain the transition between the other regimes.
Figure 5 shows the three different regimes for varying configurations of the GTmodel. When the trees are small with respect to the grid, the gridcenter node dominates congestion. Increasing the size of the trees, the congestion jumps first to the connector nodes, and later to the treeroot nodes. An appropriate parameter to know the current congestion regime is the congestion radius , defined as the distance between the maximum betweenness node and the grid center.
Once noise is added to the GTmodel using the methods in Appendix A, the regime’s transitions are expected to soften. The left panel of Fig. 5 presents the behavior of the congestion radius as a function of for fixed and . First, for small sizes of the trees, we observe an offset in the gridcenter regime, although the congestion radius remains close to the grid center (). Secondly, as tree height increases, we observe an expected noisy behavior preclusion of the transitions between the regimes. Finally, a general shift of the different transition with respect to the noiseless case is also pointed out. However, despite all, the different regimes are still clearly identifiable and stable for a wide range of values when noise is added to the GTmodel. It is worth highlighting that the abruptness of the transition remains despite the noise. As it can be seen in Supplemental Fig. S4, as we decrease the level of noise, the observed shift vanishes.
The right panel of Fig. 5 generalizes the results on the left one and analyzes, in terms of a phase diagram, the accuracy in predicting the transition between the different regimes for a large set of model parameters. As defined, the GTmodel only considers squared grids and regular trees, which probably is too restrictive to resemble real cities and. Also, it renders sparse model sampling as the parameters get large. To overcome these drawbacks, we extend the model to incorporate intermediate grid and tree sizes (besides the ones given by Eq. 2) which allows to draw GTmodel realizations of any network size. In the grid case, we generate these intermediate sizes between and by incrementally adding nodes (one by one) to the current grid periphery until we reach the desired nodes number . In this iterative process, nodes are added at random locations considering the remaining empty positions. We also implement an equivalent procedure for the tree.
Results in the right panel of Fig. 5 are intuitive: congestion occurs in the center of the grid (dark values in the phase diagram) when trees are short, i.e., grid dynamics predominate. As trees increase in size (vertical axis) a phase transition to the connector regime occurs (gray values in the diagram). At this point, the connector nodes become a bottleneck for the transportation network. Eventually, as trees keep increasing in size, the highest hierarchy nodes of trees becomes the bottleneck and then we reach the treeroot regime (light gray in the diagram). These transitions from the center to the outer bounds of the graph are reminiscent of the double percolation phase transition observed in coreperiphery networks Colomerde Simón and Boguñá (2014). Indeed, the GTmodel shares some structural features with that family of networks, which may explain the resemblance of such observation. Finally, note that the phase transitions evidenced in the left panel of Fig. 5 represent a vertical slice of the phase diagram in right one (marked as a blue vertical line).
We see that the transition between the grid center and the connector regimes, predicted by Eq. (17), is accurate in all the phase diagram (red line). The transition between the connector and the treeroot regimes, as given by Eq. (17), is only accurate at grid sizes given by Eq. (2) (black solid line with dots in Fig. 5). This is mainly because the addition of new nodes alters the betweenness of the connector and the tree root in an imbalanced way. See that, in comparison with the regular sizes of the grid (circles) we need much larger trees to trespass the phase transition. This can be considered in Eq. (17) without much effort to obtain a better prediction (black dashed line). A detailed explanation of how to correct Eq. (17) is given in Supplemental Sec. S1.
In addition to the detection of this phase transition points, our analytical development allows to understand the asymptotic behavior of the regimes. Here, the parabolic character of the transition function in Eq. (13) permits to state that the two regimes never collapse, neither reach a constant separation and the gridside area enlarges as increases. This would mean that, as cities grow larger, the internal flow predominates the dynamics of the transportation system. This is compatible with recent observations considering real transport data Louail et al. (2015).
Vi Evidence of Congestion Regimes in cities
The congestion regimes and their abrupt transitions uncovered by the GTmodel have not been previously observed in real cities. In this section, we validate the existence of these regimes, and analyze how abrupt the transitions are by applying to empirical road networks the same analysis done for the GTmodel. To this aim, we consider the road network contained within a circle of radius , using as geometric center of the city the one provided by the service www.latlong.net (2020). For each value of , we identify the set of nodes with largest betweenness, and calculate the average congestion radius as
(19) 
the average distance to the center of the city of these largest betweenness nodes.
Theoretical analysis on GTmodel predicts three different regimes delimited by two transitions. However, on real cities, these regimes may or may not exist or, alternatively, be different in number. To detect them, we use an automated method which statistically identifies change points where the congestion radius significantly changes, either in mean or slope Killick et al. (2012)
. Additionally, we make use of the elbow method (usually applied to kmeans clustering algorithm) to choose the optimal number of change points, see Supplemental Sec. S2. Subsequently, these change points define the different congestion regimes.
We have analyzed the 97 city road networks in Kirkley et al. (2018), using the data provided by the authors; a detailed description of all these cities can be read in this reference. From all of them, 49 networks present detectable regimes with multiple abrupt transitions between them, whereas the rest exhibit softer transitions or other patterns.
Figure 6 shows the results for 9 of the networks with clear multiple abrupt transitions, with radius ranging from the km of Abidjan to the km of Tianjin. Equivalent results for another 21 cities are presented in Supplemental Fig. S5. For these 30 cities, the behavior is very close to that predicted by the GTmodel. We first highlight that real cities, in general, have between 3 and 5 regimes. The additional regimes absorb noise when the transition is not as abrupt as expected. Besides this effect, we clearly observe that many cities, indeed, contain the expected regimes where congestion abruptly changes between distant geographical regions.
These results have been obtained by averaging the radius of the largest betweenness nodes for each city and radius, where in Fig. 6 and Supplemental Fig. S5. We present in Supplemental Fig. S6 a sensitivity analysis of the results in Fig. 6 for values of . This allows us to conclude that the detected pattern persists by extending our analysis beyond the single congestion node.
Among the remaining 48 networks, 43 present softer regime transitions (see Supplemental Fig. S7) and 5 of them exhibit other patterns (see Supplemental Fig. S8). This makes evident that GTmodel does not work properly for all the cities since the landscape characteristics, socioeconomic factors and historical background may have different impacts in the morphogenesis of cities Barthelemy (2018). These factors may eventually derive into different downtown layouts (other than gridlike), or different connectivity patterns between arterial roads and urban centers, which are not considered by the GTmodel. See for instance Melbourne, Rio de Janeiro, Mumbai and San Francisco in Supplemental Fig. S8, as examples. These cities present important commonalities: they are all constrained by the sea, with a shape that resembles a peninsula, and with weak connectivity among city differentiated components.
Vii Conclusions and Perspectives
We have presented the GTmodel for the analysis of dynamical properties of transportation networks. By using the model, which reproduces several wellknown properties of real transportation networks, we unveil the existence of a double congestion phase transition, which is tightly related to the geographic areas where traffic congestion emerges. Remarkably, the transitions between these regimes are abrupt, implying that they may be unpredictable by only considering the current state of the system. Consequently, taking proper actions previous to the network collapse requires a complex systems analysis. Using the GTmodel, we are able to provide analytical predictions along this direction, and reveal that the emergence of such phenomena is related to the size of the city, the way in which arterial and local roads are connected, and the size of the urban catchment area Zipf (1946); Simini et al. (2012).
We provide here another step towards the understanding of how urban growth and changes in mobility dynamics affects urban infrastructure. Occurring these transitions at long or short time scales Strano et al. (2012); Louail et al. (2015); Zeng et al. (2019), urban infrastructure is continuously evolving and, undoubtedly, congested areas (or, alternatively, dense traffic areas) will also coevolve with them. Clearly exemplified in Zeng et al. (2019), the system may transform into a radically different effective structural organization, from a lattice to a smallworld in terms of percolation. Here, we unveil a similar effect for the spatial behavior of congestion. As cities increasingly incorporate mobility from larger distances, the core of the transportation network goes from a latticelike behavior to a treelike one, causing that the areas with the least resilience to congestion abruptly change into different geographic position, and eventually concluding in the different congestion phases we identify. We provide clues of the existence of such phenomena for about 50% of the analyzed cities worldwide —observing at times more than two regime shifts. Interestingly, we also show that several other transitional patterns may emerge.
Further work, along the lines of this paper, may continue in this direction and provide information about how the architecture of road interconnectivity affects the emergence of the confirmed and alternative regimes. Although cities are currently undergoing a paradigm shift of urban mobility, ground transportation is, and will be, still prominent in the near future, and being able to adapt our transportation networks to the accelerated urban growth is of pivotal importance to optimize the cities of tomorrow.
Acknowledgements
We specially thank Alec Kirkley, Gourab Ghoshal, Hugo Barbosa and Marc Barthelemy for sharing the road network data of the cities we analyze.
N.L, J.BH. and A.SR acknowledge the support of the Spanish MICINN project (grant PGC2018096999AI00). N.L. acknowledges as well the support of a postdoctoral grant from the Universitat Oberta de Catalunya (UOC). S.G. acknowledges financial support from Spanish MINECO (grant PGC2018094754BC21), Generalitat de Catalunya (grant No. 2017SGR896), and Universitat Rovira i Virgili (grant No. 2019PFRURVB241).
Appendix A GTmodel with noise
We have tested three types of noise: (1) random edge addition with length bias; (2) random edge removal with length bias; and (3) Delaunay triangulation noise. For all noise models, edges are gradually inserted or removed until graph density is modified in the desired amount , where is the number of edges and the number of nodes of the network. Note that for planar graphs , see Chapter 2 of Barthelemy (2018). Since the noise is introduced with biases proportional to the distances between the nodes, it is necessary to assign first coordinates to the nodes.
1 Planar embedding
The purpose of the current appendix is to explain how the GTmodel network is embedded in the surface, namely how we assign to the GTmodel nodes a position in 2D. The coordinates origin, i.e., the node with position , is assumed to be located in the center of the grid, which is well defined since the grid is supposed to have sides with an odd number of nodes, (perfect grid), as shown in Fig. 1. This holds even for grids with a general size (such as in Fig. 5), because they are obtained by randomly adding new nodes to the periphery of a perfect grid. In the grid, nodes coordinates remain defined as the number of jumps required to reach the central node: counts the jumps in the horizontal direction, while in the vertical one.
It is possible to proceed in a similar way for the tree nodes. Here position of a node is defined using polar coordinates with respect to the gridcenter node:
(20) 
where

The treeroot is set to be in the same axis as the corresponding connector node, and at a distance from the grid center. This selection is useful to avoid the collision between tree and grid nodes;

is the number of jumps required to reach the node from its treeroot (i.e., the tree level);

accounts for the angular separation of node
with respect to the grid center. All nodes at the same level of the tree, and for the four trees of the GTmodel, are uniformly distributed along the circle of radius
.
We show an example of this planar embedding in Supplementary Fig. S9.
2 GTmodel with additive length bias noise
For this type of noise, we randomly add edges with a probability inversely proportional to a certain power of the euclidean distance between endpoints and . The iterative procedure works as follows: for a given pair of nodes and chosen uniformly at random, an edge is added with probability , provided that planarity restrictions are not compromised. The value of controls the bias towards the introduction of new edges.
3 GTmodel with negative length bias noise
This kind of noise is implemented following the same procedure as for additive noise, with the only difference that now edges are removed, rather than added.
4 GTmodel with Delaunay noise
This type of noise is generated considering the Delaunay triangulation of the GTmodel nodes, mimicking the procedure in Kirkley et al. (2018). Once the triangulation is generated, edges, uniformly chosen at random, are gradually inserted to the base model until the desired edge density is reached.
Appendix B Betweenness of connector nodes of the GTmodel
The calculation of the betweenness of the connector nodes of the GTmodel, i.e., the nodes in the center of the sides of the grid to which the root of the trees are connected, can be done following the same approach as in Sec. IV. First, we decompose the betweenness in three contributions using Eq. (5):
(21) 
Let us consider for example the connector node to tree in Fig. 1. All the shortest paths coming from nodes in the other three trees have to pass through it, thus
(22) 
Similarly, all the paths starting in nodes of the grid and going to the tree also cross our connector node, contributing to its betweenness with one unity per origin node, i.e., with a term . Additionally, this connector also participates in other paths between the grid and the other trees. More precisely, if the origin is a node in the same side of the grid as the connector, there are two trees with shortest paths through the connector. For example, if we take as origin the node which is at a distance below the considered connector in Fig. 1, there is one path crossing the connector among the shortest paths to arrive to tree , and paths through the connector among the to arrive to tree . Given the updown symmetry of the system, the final expression for coefficient is
(23) 
Finally, shortest paths that start and end in the grid and cross a connector node need again that one of the endpoints is in the same side as the connector, thus we choose again as origin a node at a distance below the previously considered connector. The destination node can be identified with variables , the horizontal (to the left) and vertical (upwards) distances to the connector node, respectively. The case consists of destinations in the same side as the origin and connector, thus contributing to the betweenness of the connector with a value . When there are paths through the connector node among the total shortest paths connecting the origin and destination nodes, thus we get:
(24) 
Appendix C Betweenness of tree nodes of the GTmodel
The symmetries of full and complete trees allow for the calculation of the betweenness of all their nodes. In fact, all nodes of the tree located at the same level share the same value of the betweenness, thus we can denote it as , where level is for the root and for the leaves of the tree.
Trees are characterized by the absence of cycles. As a consequence, there is a unique path connecting every pair of nodes, which means that all , thus simplifying Eq. (1).
Let us consider a node at level of the tree. There are two types of paths that cross it: paths that come from one children (level ) and continue to one of its siblings (level ); paths that come from the parent (level ) and continue to one of the children (level ). We need to count how many different paths exist for each of these types.
In the first case, for each of the pairs of children, there are possible origins of the path, and the same number of possible destinations, thus forming a total of different paths. Here, we have made use of Eq. (2), which provides the number of nodes in a full and complete tree with branching ratio and height :
(25) 
In our case, we have applied it to calculate the number of nodes of the subtree formed by a child from level and all its descendants.
In a similar way, the number of paths that cross the node and its parent is equal to the number of descendants of the node, , multiplied by the number of the rest of the nodes, . Combining both results, the betweenness of a node at level reads:
(26) 
which can be written as:
(27) 
This expression is valid for all nodes of the tree, including the root (). In particular, betweenness vanishes for the leaves, , as expected.
It is worth noting that maximum betweenness of the tree is located at the root only for trees with branching ratio ; binary trees have the maximum at the children of the root. This can be shown by calculating the difference of betweenness between levels and :
(28) 
The term in brackets is negative if and . To obtain Eq. (28), we have made use of the property
(29) 
Once we have determined the betweenness within the tree, we need to include the contribution of the rest of the network which forms the GTmodel. The new paths to consider are those starting outside the tree, with destination in a node descendant of the one for which we want to calculate the betweenness. If this node belongs to level , following the same procedure which has led to Eq. (26), the result is
(30) 
Note that . Now, we obtain the final expression for the desired betweenness of the treeroots of the GTmodel, :
(31) 
For binary trees (), the consideration of the full GTmodel network makes the root of the tree become the node of maximum betweenness among the rest of the nodes in the tree:
(32) 
This time, the term in brackets is positive for all values of the branching ratio, height of the tree, and size of the grid.
References
 Bettencourt and West (2010) L. Bettencourt and G. West, A unified theory of urban living, Nature 467, 912 (2010).
 Batty (2012) M. Batty, Building a science of cities, Cities 29, S9 (2012), current Research on Cities.
 Helbing (2015) D. Helbing, Traffic Theory from First Principles, Available at SSRN 2960224 (2015).
 Godfrey (1969) J. Godfrey, The mechanism of a road network, Traffic Engineering & Control 8 (1969).
 Daganzo and Geroliminis (2008) C. F. Daganzo and N. Geroliminis, An analytical approximation for the macroscopic fundamental diagram of urban traffic, Transportation Research Part B: Methodological 42, 771 (2008).
 Barthelemy and Flammini (2009) M. Barthelemy and A. Flammini, Coevolution of Density and Topology in a Simple Model of City Formation, Networks and Spatial Economics 9, 401 (2009).
 Balcan et al. (2009) D. Balcan, V. Colizza, B. Gonçalves, H. Hu, J. J. Ramasco, and A. Vespignani, Multiscale mobility networks and the spatial spreading of infectious diseases, Proceedings of the National Academy of Sciences 106, 21484 (2009), https://www.pnas.org/content/106/51/21484.full.pdf .
 Guimerà et al. (2002) R. Guimerà, A. DíazGuilera, F. VegaRedondo, A. Cabrales, and A. Arenas, Optimal Network Topologies for Local Search with Congestion, Phys. Rev. Lett. 89, 248701 (2002).
 Echenique et al. (2005) P. Echenique, J. GómezGardeñes, and Y. Moreno, Dynamics of jamming transitions in complex networks, Europhysics Letters (EPL) 71, 325 (2005).
 Ling et al. (2010) X. Ling, M.B. Hu, R. Jiang, and Q.S. Wu, Global dynamic routing for scalefree networks, Physical Review E 81, 016113 (2010).
 SoléRibalta et al. (2018) A. SoléRibalta, S. Gómez, and A. Arenas, Decongestion of Urban Areas with Hotspot Pricing, Networks and Spatial Economics 18, 33 (2018).
 Akbarzadeh and Estrada (2018) M. Akbarzadeh and E. Estrada, Communicability geometry captures traffic flows in cities, Nature human behaviour 2, 645 (2018).
 Verbavatz and Barthelemy (2019) V. Verbavatz and M. Barthelemy, Critical factors for mitigating car traffic in cities, PLoS one 14 (2019).
 Gao et al. (2019) L. Gao, P. Shu, M. Tang, W. Wang, and H. Gao, Effective trafficflow assignment strategy on multilayer networks, Physical Review E 100, 012310 (2019).
 Chen et al. (2020) J. Chen, M.B. Hu, and M. Li, Trafficdriven epidemic spreading in multiplex networks, Physical Review E 101, 012301 (2020).
 Wang et al. (2012) P. Wang, T. Hunter, A. M. Bayen, K. Schechtner, and M. C. González, Understanding Road Usage Patterns in Urban Areas, Scientific Reports 2, 1001 (2012).
 Strano et al. (2012) E. Strano, V. Nicosia, V. Latora, S. Porta, and M. Barthelemy, Elementary processes governing the evolution of road networks, Scientific Reports 2, 296 (2012).
 Olmos et al. (2018) L. E. Olmos, S. Çolak, S. Shafiei, M. Saberi, and M. C. González, Macroscopic dynamics and the collapse of urban traffic, Proceedings of the National Academy of Sciences 115, 12654 (2018).
 Zhang et al. (2019) L. Zhang, G. Zeng, D. Li, H.J. Huang, H. E. Stanley, and S. Havlin, Scalefree resilience of real traffic jams, Proceedings of the National Academy of Sciences 116, 8673 (2019).
 Zeng et al. (2019) G. Zeng, D. Li, S. Guo, L. Gao, Z. Gao, H. E. Stanley, and S. Havlin, Switch between critical percolation modes in city traffic dynamics, Proceedings of the National Academy of Sciences 116, 23 (2019).
 SoléRibalta et al. (2016) A. SoléRibalta, S. Gómez, and A. Arenas, Congestion Induced by the Structure of Multiplex Networks, Phys. Rev. Lett. 116, 108701 (2016).
 Kirkley et al. (2018) A. Kirkley, H. Barbosa, M. Barthelemy, and G. Ghoshal, From the betweenness centrality in street networks to structural invariants in random planar graphs, Nature Communications 9, 2501 (2018).
 Wegman and Aarts (2006) F. C. Wegman and L. Aarts, Advancing sustainable safety: National Road Safety Outlook for 2005–2020., (2006).
 Freeman (1977) L. C. Freeman, A Set of Measures of Centrality Based on Betweenness, Sociometry 40, 35 (1977).
 Freeman (1978) L. C. Freeman, Centrality in social networks conceptual clarification, Social Networks 1, 215 (1978).
 Goh et al. (2003) K.I. Goh, E. Oh, B. Kahng, and D. Kim, Betweenness centrality correlation in social networks, Physical Review E 67, 017101 (2003).
 Everett and Borgatti (2005) M. Everett and S. P. Borgatti, Ego network betweenness, Social networks 27, 31 (2005).
 Leydesdorff (2007) L. Leydesdorff, Betweenness centrality as an indicator of the interdisciplinarity of scientific journals, Journal of the American Society for Information Science and Technology 58, 1303 (2007).
 Kourtellis et al. (2013) N. Kourtellis, T. Alahakoon, R. Simha, A. Iamnitchi, and R. Tripathi, Identifying high betweenness centrality nodes in large social networks, Social Network Analysis and Mining 3, 899 (2013).
 De Arruda et al. (2014) G. F. De Arruda, A. L. Barbieri, P. M. Rodríguez, F. A. Rodrigues, Y. Moreno, and L. da Fontoura Costa, Role of centrality for the identification of influential spreaders in complex networks, Physical Review E 90, 032812 (2014).
 Girvan and Newman (2002) M. Girvan and M. E. Newman, Community structure in social and biological networks, Proceedings of the National Academy of Sciences USA 99, 7821 (2002).
 Newman and Girvan (2004) M. E. Newman and M. Girvan, Finding and evaluating community structure in networks, Physical review E 69, 026113 (2004).
 Matamalas et al. (2018) J. T. Matamalas, A. Arenas, and S. Gómez, Effective approach to epidemic containment using link equations in complex networks, Science advances 4, eaau4212 (2018).
 Xia et al. (2010) Y. Xia, J. Fan, and D. Hill, Cascading failure in Watts–Strogatz smallworld networks, Physica A: Statistical Mechanics and its Applications 389, 1281 (2010).
 Wandelt et al. (2018) S. Wandelt, X. Sun, D. Feng, M. Zanin, and S. Havlin, A comparative analysis of approaches to networkdismantling, Scientific reports 8, 1 (2018).
 Holme et al. (2002) P. Holme, B. J. Kim, C. N. Yoon, and S. K. Han, Attack vulnerability of complex networks, Physical review E 65, 056109 (2002).
 Wang and Rong (2009) J.W. Wang and L.L. Rong, Cascadebased attack vulnerability on the US power grid, Safety science 47, 1332 (2009).
 Iyer et al. (2013) S. Iyer, T. Killingback, B. Sundaram, and Z. Wang, Attack robustness and centrality of complex networks, PloS one 8 (2013).
 Bellingeri et al. (2014) M. Bellingeri, D. Cassi, and S. Vincenzi, Efficiency of attack strategies on complex model and realworld networks, Physica A: Statistical Mechanics and its Applications 414, 174 (2014).
 Barthelemy (2004) M. Barthelemy, Betweenness centrality in large complex networks, The European physical journal B 38, 163 (2004).
 SoléRibalta et al. (2014) A. SoléRibalta, M. De Domenico, S. Gómez, and A. Arenas, Centrality rankings in multiplex networks, in Proceedings of the 2014 ACM conference on Web science (2014) pp. 149–155.
 Wang et al. (2015) J. Wang, B. Xu, and Y. Wu, Ability paradox of cascading model based on betweenness, Scientific reports 5, 13939 (2015).
 De Domenico et al. (2015) M. De Domenico, A. SoléRibalta, E. Omodei, S. Gómez, and A. Arenas, Ranking in interconnected multilayer networks reveals versatile nodes, Nature communications 6, 1 (2015).
 Zhao et al. (2005) L. Zhao, Y.C. Lai, K. Park, and N. Ye, Onset of traffic congestion in complex networks, Physical Review E 71, 026125 (2005).
 Yan et al. (2006) G. Yan, T. Zhou, B. Hu, Z.Q. Fu, and B.H. Wang, Efficient routing on complex networks, Physical Review E 73, 046108 (2006).
 Liu et al. (2007) Z. Liu, M.B. Hu, R. Jiang, W.X. Wang, and Q.S. Wu, Method to enhance traffic capacity for scalefree networks, Physical Review E 76, 037101 (2007).
 Dolev et al. (2010) S. Dolev, Y. Elovici, and R. Puzis, Routing betweenness centrality, Journal of the ACM (JACM) 57, 1 (2010).
 Dong et al. (2012) J.Q. Dong, Z.G. Huang, Z. Zhou, L. Huang, Z.X. Wu, Y. Do, and Y.H. Wang, Enhancing transport efficiency by hybrid routing strategy, EPL (Europhysics Letters) 99, 20007 (2012).
 Tan et al. (2014) F. Tan, J. Wu, Y. Xia, and K. T. Chi, Traffic congestion in interconnected complex networks, Physical Review E 89, 062813 (2014).
 SoléRibalta et al. (2016) A. SoléRibalta, S. Gómez, and A. Arenas, A model to identify urban traffic congestion hotspots in complex networks, Royal Society open science 3, 160098 (2016).
 SoléRibalta et al. (2018) A. SoléRibalta, S. Gómez, and A. Arenas, Decongestion of urban areas with hotspot pricing, Networks and Spatial Economics 18, 33 (2018).
 Manfredi et al. (2018) S. Manfredi, E. Di Tucci, and V. Latora, Mobility and congestion in dynamical multilayer networks with finite storage capacity, Physical review letters 120, 068301 (2018).
 SoléRibalta et al. (2019) A. SoléRibalta, A. Arenas, and S. Gómez, Effect of shortest path multiplicity on congestion of multiplex networks, New Journal of Physics 21, 035003 (2019).
 Newman (2005) M. E. J. Newman, A measure of betweenness centrality based on random walks, Social Networks 27, 39 (2005).
 Estrada et al. (2012) E. Estrada, N. Hatano, and M. Benzi, The physics of communicability in complex networks, Physics Reports 514, 89 (2012).
 Quercia et al. (2014) D. Quercia, R. Schifanella, and L. M. Aiello, The shortest path to happiness: Recommending beautiful, quiet, and happy routes in the city, in Proceedings of the 25th ACM conference on Hypertext and social media (ACM, 2014) pp. 116–125.
 Brandes (2001) U. Brandes, A faster algorithm for betweenness centrality, Journal of mathematical sociology 25, 163 (2001).
 Colomerde Simón and Boguñá (2014) P. Colomerde Simón and M. Boguñá, Double Percolation Phase Transition in Clustered Complex Networks, Phys. Rev. X 4, 041020 (2014).
 Louail et al. (2015) T. Louail, M. Lenormand, M. Picornell, O. G. Cantú, R. Herranz, E. FriasMartinez, J. J. Ramasco, and M. Barthelemy, Uncovering the spatial structure of mobility networks, Nature Communications 6, 1 (2015).
 www.latlong.net (2020) www.latlong.net, Latitude and Longitude Finder (2020 (accessed May 18, 2020)).
 Killick et al. (2012) R. Killick, P. Fearnhead, and I. A. Eckley, Optimal detection of changepoints with a linear computational cost, Journal of the American Statistical Association 107, 1590 (2012).
 Barthelemy (2018) M. Barthelemy, Morphogenesis of spatial networks (Springer, 2018).
 Zipf (1946) G. K. Zipf, The P 1 P 2/D hypothesis: on the intercity movement of persons, American sociological review 11, 677 (1946).
 Simini et al. (2012) F. Simini, M. C. González, A. Maritan, and A.L. Barabási, A universal model for mobility and migration patterns, Nature 484, 96 (2012).
 Thorndike (1953) R. L. Thorndike, Who belongs in the family?, Transportation Research Part B: Methodological 18, 267 (1953).
S1 Congestion regime in noncomplete grids
Analytical betweenness expressions in Sec. 4 have been derived assuming the case of complete grids, i.e. grids with side () and nodes. In Fig. 5, we also introduced incomplete grids, to fill the gaps between grids of oddsquared sizes. These incomplete grids, with extra nodes in the periphery, modify differently the values of the betweenness of the connector and treeroot nodes, thus shifting the transition between these regimes.
Consider Fig. S1 as an illustration of the following process. We start by connecting a new node to the left side of a complete grid, and quantify its contribution to the betweenness of the connector node (belonging to the side in front of the new node), and the adjacent treeroot, . After adding , nodes and , among others, experience an increment in its betweenness that can be formalized as:
(S1)  
(S2) 
The value of includes the contribution to betweenness of paths between and the nodes of the tree to which node belongs to. Since all paths need to cross to reach their destinations, this value is equivalent to the number of nodes in the tree minus one. These paths also cross the connector and contribute to , see the black path in Fig. S1. However, embodies a new term, , that considers the paths between the new node and the gridones located in the same side as the connector , and above it, see the green paths in Fig. S1. It turns out that
(S3) 
which explains why, in Fig. 5, numerical simulations associated to the connector regime overcome the solid black frontier defined by Eq. (17). Formally, we may write
(S4) 
It can be approximated by
(S5) 
where we have taken advantage of the same idea used to derive the term in Eq. (B4). This is an approximation because we are supposing that the side in which node is located is also full of new nodes, above and below it. This gives a good upper bound for most configurations, which is enough to obtain the corrected transition boundary depicted as a dashed line in the right panel of Fig. 5.
S2 Detection of the number of congestion regimes
Theoretical analysis based on GTmodel predicts three different phases that can be clearly defined by two cut points (a.k.a. change points). To identify these pattern in empirical road networks (see Fig. 6 in the main text), one has to decide the number of change points to consider. Note that, as the number of change points increases, the fitting error decreases. To automatically decide the optimal number of change points, we recall to the elbow test introduced in Thorndike (1953). The method is based on the concept of diminishing returns to balance the accuracy obtained with respect to the number of change points considered.
In Fig. S2 we plot the evolution of the mean squared error (MSE) of the fit with respect to the number of change points. As expected, the resulting line draws an elbow: in general, the error rapidly decreases as the number of change points grows, but after a certain value, adding another change point doesn’t provide much improvement. Such a surplus of precision can be considered a kind of overfitting. Of course, the opposite situation, namely a very low number of change points, leads to underfitting. Thus, the elbow singles out the optimal number of change points. In Fig. S2 we see that the elbow position approximately falls between 2 and 4 change points, endorsing the GTmodel prediction.
Comments
There are no comments yet.