From one-way streets to percolation on random mixed graphs

Abstract

In most studies, street networks are considered as undirected graphs while one-way streets and their effect on shortest paths are usually ignored. Here, we first study the empirical effect of one-way streets in about $140$ cities in the world. Their presence induces a detour that persists over a wide range of distances and characterized by a non-universal exponent. The effect of one-ways on the pattern of shortest paths is then twofold: they mitigate local traffic in certain areas but create bottlenecks elsewhere. This empirical study leads naturally to consider a mixed graph model of 2d regular lattices with both undirected links and a diluted variable fraction $p$ of randomly directed links which mimics the presence of one-ways in a street network. We study the size of the strongly connected component (SCC) versus $p$ and demonstrate the existence of a threshold $p_c$ above which the SCC size is zero. We show numerically that this transition is non-trivial for lattices with degree less than $4$ and provide some analytical argument. We compute numerically the critical exponents for this transition and confirm previous results showing that they define a new universality class different from both the directed and standard percolation. Finally, we show that the transition on real-world graphs can be understood with random perturbations of regular lattices. The impact of one-ways on the graph properties were already the subject of a few mathematical studies, and our results show that this problem has also interesting connections with percolation, a classical model in statistical physics.

arXiv comment11 pages, 3 tables, 11 figures

References in corpus (21)

• Random graphs with arbitrary degree distributions and their applications
• Network robustness and fragility: Percolation on random graphs
• OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks
• Centrality Measures in Spatial Networks of Urban Streets
• Scaling laws in the spatial structure of urban road networks
• Urban Spatial Order: Street Network Orientation, Configuration, and Entropy
• Giant strongly connected component of directed networks
• Percolation in Directed Scale-Free Networks
• From the betweenness centrality in street networks to structural invariants in random planar graphs
• Low-density series expansions for directed percolation I: A new efficient algorithm with applications to the square lattice
• Generalized percolation in random directed networks
• Urban street networks: a comparative analysis of ten European cities
• Local structure of directed networks
• Critical factors for mitigating car traffic in cities
• Conductivity of continuum percolating systems
• Elementary processes governing the evolution of road networks
• Crossover from Isotropic to Directed Percolation
• Percolation on Isotropically Directed Lattice
• Random Resistor-Diode Networks and the Crossover from Isotropic to Directed Percolation
• The elastic and directed percolation backbone
• Perturbing the Shortest Path on a Critical Directed Square Lattice

Cited by in corpus (7)

• Strong Connectivity in Real Directed Networks
• On the stability of traffic breakup patterns in urban networks
• A review of the structure of street networks
• Percolation in Networks of Liquid Diodes
• Solving a directed percolation inverse problem
• Janus Percolation in Anisotropic Limited-Degree Networks
• Nonreciprocal random networks and their percolation properties