Dynamics of functional failures and recovery in complex road networks

We propose a new framework for modeling the evolution of functional failures and recoveries in complex networks, with traffic congestion on road networks as the case study. Differently from conventional approaches, we transform the evolution of functional states into an equivalent dynamic structural process: dual-vertex splitting and coalescing embedded within the original network structure. The proposed model successfully explains traffic congestion and recovery patterns at the city scale based on high-resolution data from two megacities. Numerical analysis shows that certain network structural attributes can amplify or suppress cascading functional failures. Our approach represents a new general framework to model functional failures and recoveries in flow-based networks and allows understanding of the interplay between structure and function for flow-induced failure propagation and recovery.

Figure 1

Illustration of functional dual mapping and the vertex split-recovery process. (a) Primal representation of a road network; roads are labeled as numbers, and intersections as letters. (b) Dual representation of the road network in (a). (c), (d) Split and recovery of dual vertex 2 due to congestion on the HE segment of road 2.

Figure 2

Plots of the evolution of dual degree distributions for function-augmented dual networks: (a) Beijing road network (12/14/2015); (b) Shanghai road network (7/7/2016). The black line and the colored lines represent the degree distribution of the base dual network and the function-augmented dual networks at different times of day. Logarithmic binning is used for better clarity. The degree distribution of the base dual network can be fitted to a power-law distribution, $p\left(k\right)\sim k^{-\gamma }$, for $k\ge k_{\min }=3$, $\gamma =2.58$ (Beijing) and $k\ge k_{\min }=4$, $\gamma =2.48$ (Shanghai).

Figure 3

Behavior of the vertex split-recovery process using the 7-day congestion evolution data from the Beijing road network. (a) Plot of the normalized vertex- split probability. The $y$ axis is the normalized vertex-split probability ${\overline{P}}_s\left(k\right)/\overline{P}\left(k\right)$. $\overline{P}\left(k\right)$ and ${\overline{P}}_s\left(k\right)$ are the average proportions of degree $k$ dual vertices and degree $k$ dual vertices with vertex split in the function-augmented dual networks. Both $\overline{P}\left(k\right)$ and ${\overline{P}}_s\left(k\right)$ are obtained by averaging the results from function-augmented dual networks at all time steps during the day. (b) Probability distribution of the degree ratio $R_k$ for binary vertex splits, which can be fitted to a beta distribution $\left[\beta (1.697,1.697)\right]$. (c) Distribution of the duration time $t$ between the time at which the vertex gets split and the time at which it recovers, which can be approximated by an exponential distribution.

Figure 4

Illustration of the ranked planar tree representation of the vertex-splitting history. Road $A$ (dual degree $k=5$) experiences congestion at time $t_1$ and $t_2$, which results in two dual-vertex splits. Under the ranked planar tree representation, it can be represented as two consecutive branchings of the tree.

Figure 5

Monte Carlo simulation results of the expected proportion of the degree $i$ split subvertices after $S$ splits $[m_i(k,S)/(S+1)]$ for degree $k$ dual vertices: (a) $k=10$; (b) $k=100$. Computed using 50 000 simulation runs of the generating process of the microscopic-level model.

Figure 6

Evolution of dual degree distributions for (a) the Beijing road network (12/10/2015) and (b) the Shanghai road network (7/11/2016). The top figures are the road speed plots at three sample time steps. The bottom figures present the corresponding dual-vertex degree distributions for (i) the base dual network (no congestion), (ii) the function-augmented dual network (actual congestion scenario), (iii) network configurations predicted by the vertex split-recovery model under different DBMF approximation schemes (no degree correlation and general degree correlation), and (iv) the power law with exponential cutoff fittings of the dual degree distributions.

Figure 7

Fitting result for $w_1\left(t\right)$ using the DBMF approximation with the general degree correlation.

Figure 8

Comparison of the total number of dual vertices from empirical data (red line) and the expected total number of dual vertices ($N^{*}$) obtained from the vertex split-recovery model for the Beijing and Shanghai road networks.

Figure 9

Comparison of the total number of unrecovered vertex splits at each time step in the empirical data (red line) and the expected number of vertex splits ($N^{\mathrm{ES}}$) obtained from the vertex split-recovery model for the Beijing and Shanghai road networks.

Figure 10

Impact of $w_1$ on the expected level of functional loss [$N_k^{\mathrm{ES}}/(k-1)$] for dual vertices of different degrees ($w_2=0.1$, $w_3=0$).

Figure 11

Comparison of network performance under different normalized network loading levels. (a) Impact of $w_1$ on the average probability that a dual vertex has a split neighbor under the stationary solution (${\varphi }^{*}$). Obtained by solving for the stationary solution under the DBMF approximation with no degree correlation assumption. (b), (c) Plots of the dual degree distributions of the Beijing and Shanghai road networks under the same set of normalized network loading levels. The light-traffic condition is taken as the typical $w_1$ value in late-night hours; the heavy-traffic condition is selected as the typical peak-hour $w_1$ value.

Figure 12

Relationship of the parameters of the power law with an exponential cutoff distribution and the fitted $w_1$ value. (a), (b) Linear fitting of the $\gamma -w_1$ and $\kappa -w_1$ relationships for the Beijing road network (12/11/2015). (c), (d) Linear fitting of the $\gamma -w_1$ and $\kappa -w_1$ relationships for the Shanghai road network (7/11/2016).