Multiple abrupt phase transitions in urban transport congestion

During the last decades, the study of cities has been transformed by new approaches combining engineering and complexity sciences. Network theory is playing a central role, facilitating the quantitative analysis of crucial urban dynamics, such as mobility, city growth, or urban planning. In this work we focus on the spatial aspects of congestion. Analyzing a large amount of real city networks, we show that the location of the onset of congestion changes according to the considered urban area, defining, in turn, a set of congestion regimes separated by abrupt transitions. To help unveiling this spatial dependencies of congestion (in terms of network betweenness analysis), we introduce a family of planar road network models composed by a dense urban center connected to an arboreal periphery. These models, coined as GT and DT-MST models, allow us to analytically, numerically, and experimentally describe how and why congestion emerges in particular geographical areas of monocentric cities and, subsequently, to describe the congestion regimes and the factors that promote the appearance of their abrupt transitions. We show that the fundamental ingredient behind the observed abrupt transitions is the spatial separation between the urban center and the periphery, and the number of separated areas that form the periphery. Elaborating on the implications of our results, we show that they may have influence in the design and optimization of road networks regarding urban growth and the management of daily traffic dynamics.

Figure 1

Betweenness distribution of the road networks of three cities, Phoenix (AZ, USA), Medan (Indonesia), and Surat (India), compared with a GT model without noise (red dotted line), and GT model with three different kinds of noise: biased edge addition, biased edge removal, and Delaunay. The bottom right panel shows a $QQ$ plot between the real (cities) and experimental (GT model) betweenness distributions. The $QQ$ plot refers to the quantiles of the distribution obtained by the GT model (vertical axis) against those related to the empirical one (horizontal axis). Similarity between the distributions improves as the $QQ$ plot approaches the bisector, the gray solid straight line. GT-model parameters are $w=31$, $r=2$, and $h=9$, while noise has been generated until density $\rho =0.52$ is obtained for the gravity and Delaunay type, and $\rho =0.4$ for the negative one.

Figure 2

Diagram of a network generated with the GT model, with parameters $w=2\ell +1$, $r=2$, and $h=3$. The maximum betweenness can be located at the grid-center node (in red), the connector nodes (marked with a double circle), or the tree-root nodes (marked with a star). Colors, labels, and notation are set to explain the analytical computation of the betweenness of the central node of the grid, see Sec. 4.

Figure 3

Comparison between the real (bottom) and estimated (top) relationship between nodes geographic position and their betweenness for small (Dalian, China), medium (Medan, Indonesia), and big cities (Tokyo, Japan) from the left to the right. The GT models used have parameters $w=51$, $r=2$ with $h=1,3,5$, from the left to the right. Additive noise is also added in terms of relative increments of network density $\mathrm{\Delta }\rho /\rho =1.5\%$ (see Appendix pp1-s2). All distances and betweenness are normalized between 0 and 1. Coordinates for the nodes of the GT model have been assigned using the planar embedding described in Appendix pp1-s1. Solid lines on the scatter plots represent the 80 centiles of the betweenness distribution at the given radius $R$; similar results for the mean and standard deviations are provided in Fig. S2 of the Supplemental Material [68].

Figure 4

Comparison between the analytical and numerical betweenness for the grid's central node $B^{\left(\text{gc}\right)}$ (top), connector node $B^{\left(c\right)}$ (middle), and tree-root node $B^{\left(t\right)}$ (bottom) of the GT model. Analytical values are obtained by means of Eq. (5), while numerical ones are calculated using the Brandes algorithm [71]. Both $B^{\left(\text{gc}\right)}$ and $B^{\left(c\right)}$ are obtained by varying $w\in [3,40]$ at $r=h=2$, while $B^{\left(t\right)}$ is treated as a function of $r\in [3,30]$ at fixed $h=2$ and $w=5$.

Figure 5

Congestion phase space of the GT model, showing the three regimes and their transitions. Left: Solid black lines refer to the regimes as predicted by Eq. (17), with $w=25$ and $r=2$. Circles represent the experimental results after the addition of noise. Each circle is located at the statistical mode (here indicated by $R_c^{*}$) obtained with the distribution of $R_c$ after 150 realizations. The color of the circle shows the probability of that value over the experimental $R_c$ distribution. See Figs. S4 and S5 of the Supplemental Material [68] for an equivalent analysis with lower and higher levels of noise ($\mathrm{\Delta }\rho /\rho =0.2\%$ and $23\%$, respectively), which show that the transitions persist even for high levels of noise, and their shift to the right vanishes with low noise. Right: Average distance, in GT model, between the maximum betweenness node and the grid center as a function of the number of nodes of the grid $N_G$ and the trees $N_T$, for a fixed value of the branch parameter $r=2$. Average is carried out over 20 model configurations with noise $\mathrm{\Delta }\rho /\rho =0.2\%$. The result is normalized considering the maximum obtained over the set of configurations related to the same grid size ($N_G$). Red line corresponds to the estimated frontier between the grid-center and the connector regime, while black lines (solid and dashed) correspond to the transition between the connector regime and tree-root one, as predicted by Eq. (17). Blue vertical line highlights the system at $N_G=w^2={25}^2$ and corresponds to the results of the left panel.

Figure 6

Spatial behavior of congestion nodes for the random planar models introduced in Sec. 6, generated from a GT-model realization with $w=35$, $h=9$, and $r=2$. Each column corresponds to a different amount of the spatial noise, i.e., to different values of $\mathrm{\Delta }N/N$. In the upper row, the resulting network configurations are shown, with MST and DT edges painted in red and black, respectively. Hexagonal bins provide information about the occurrence of congestion nodes in space, and their colors show the related frequency in proportion to the intensity. In the bottom row we present the dependence of the congestion radius $R_c$ on the patch radial size $R_p$, i.e., the radius of the circle centered in the middle of the network, that is used to define the considered subgraph within this radius. The congestion radius range is divided into bins, and each point is located at the statistical mode $R_c^{*}$ obtained with the distribution of $R_c$ after 100 realizations, as in Fig. 5. The color of the circular markers shows the probability of that value over the experimental $R_c$ distribution. Shadow areas represent the variance of the different realizations of $R_c$ values with respect to the bin average value. The red solid line represents the GT model as presented in Sec. 3, without any noise addition.

Figure 7

Analysis of congestion regimes for nine cities. Points represent the average distance from city center of the $\lambda =15$ nodes with largest betweenness. Vertical lines indicate the change points. Plots are normalized between 0 and 1 considering the radius of the different cities. Regimes and transitions have been automatically detected by the unsupervised method described in Appendix pp5.

Figure 8

Spatial behavior of the congestion nodes for the city of Baghdad. On the left we present the dependence of the quantity introduced in Eq. (19) with $\lambda =15$, as a function of the patch radius $R_p$, as well as in Fig. 7. It is possible to detect the existence of three congestion regimes, marked with different colors, associated with different city areas where congestion occur. These can be recognized on the right, where we show the map of the city, with the congestion nodes related to each regime. Precisely, for each value of $R_p$ we plot the corresponding $\lambda$ high betweenness nodes, with a color of the regime they belong to. In the gray regime, congestion nodes are located in the city center, while in the blue one they fall on its perimeter. For the green one, congestion is mostly located at the connections between the city center and peripheral arterial roads.

Figure 9

Several examples of real cities that present softer regime transitions between the identified regimes. Points represent the average distance from city center of the $\lambda =15$ nodes with largest betweenness. Vertical lines indicate the change points. Plots are normalized between 0 and 1 considering the radius of the different cities. Regimes and transitions have been automatically detected by the unsupervised method described in Appendix pp5.

Figure 10

Example of the planar embedding of the GT model with parameters $w=7$, $r=2$, and $h=3$.

Figure 11

Graphical representation of a network generated with the GT model with parameters $w=2\ell +1$, $r=2$, and $h=3$, in which an additional node $n_o$ has been attached to periphery. Colors, labels, and notation are set to explain the derivation in Appendix pp4.

Figure 12

Relationship between fitting error (MSE) and the number of change points used to approximate the curves in Fig. 7.