From the betweenness centrality in street networks to structural invariants in random planar graphs

Abstract

We demonstrate that the distribution of betweenness centrality (BC), a global structural metric based on network flow, is an invariant quantity in most planar graphs. We confirm this invariance through an empirical analysis of street networks from 97 of the most populous cities worldwide, at scales significantly larger than previous studies. We also find that the BC distribution is robust to major alterations in the network, including significant changes to its topology and edge weight structure, indicating that the only relevant factors shaping the distribution are the number of nodes and edges as well as the constraint of planarity. Through simulations of random planar graph models and analytical calculations on Cayley trees, this invariance is demonstrated to be a consequence of a bimodal regime consisting of an underlying tree structure for high BC nodes, and a low BC regime arising from the presence of loops providing local path alternatives. Furthermore, the high BC nodes display a non-trivial spatial dependence, with increasing spatial correlation as a function of the number of edges, leading them to cluster around the barycenter at large densities. Our results suggest that the spatial distribution of the BC is a more accurate discriminator when comparing patterns across cities. Moreover, the BC being a static predictor of congestion in planar graphs, the observed invariance and spatial dependence has practical implications for infrastructural and biological networks. In particular, for the case of street networks, as long as planarity is conserved, bottlenecks continue to persist, and the effect of planned interventions to alleviate structural congestion will be limited primarily to load redistribution, a feature confirmed by analyzing 200 years of data for central Paris.

arXiv commentSupporting information in the ancillary files

References in corpus (29)

• Random graphs with arbitrary degree distributions and their applications
• Spatial Networks
• Centrality Measures in Spatial Networks of Urban Streets
• Betweenness Centrality in Large Complex Networks
• Scaling laws in the spatial structure of urban road networks
• Structural Properties of Planar Graphs of Urban Street Patterns
• Understanding Road Usage Patterns in Urban Areas
• A Topological Pattern of Urban Street Networks: Universality and Peculiarity
• The Price of Anarchy in Transportation Networks: Efficiency and Optimality Control
• Networks and Cities: An Information Perspective
• Crossover from Scale-Free to Spatial Networks
• Urban characteristics attributable to density-driven tie formation
• Congestion and centrality in traffic flow on complex networks
• Random planar graphs and the London street network
• Transport in weighted networks: Partition into superhighways and roads
• Scale Invariance in Road Networks
• The Large Scale Curvature of Networks
• Urban street networks: a comparative analysis of ten European cities
• Urban road networks -- Spatial networks with universal geometric features? A case study on Germany's largest cities
• Morphology of travel routes and the organization of cities
• Shortest paths and load scaling in scale-free trees
• Euclidean versus hyperbolic congestion in idealized versus experimental networks
• Effect of congestion costs on shortest paths through complex networks
• Hierarchical ordering of reticular networks
• Interplay between function and structure in complex networks
• Scale-Invariant Random Spatial Networks
• Betweenness Centrality in Dense Random Geometric Networks
• Intra-City Urban Network and Traffic Flow Analysis from GPS Mobility Trace
• Central loops in random planar graphs

Cited by in corpus (31)

• A city of cities: Measuring how 15-minutes urban accessibility shapes human mobility in Barcelona
• Multimodal urban mobility and multilayer transport networks
• Uncovering the socioeconomic facets of human mobility
• Morphology of travel routes and the organization of cities
• Growing Urban Bicycle Networks
• Impact of urban structure on infectious disease spreading
• Betweenness centrality of teams in social networks
• Automated Detection of Missing Links in Bicycle Networks
• Contrasting social and non-social sources of predictability in human mobility
• The impact of inter-city mobility on urban welfare
• The shape of shortest paths in random spatial networks
• Multiple abrupt phase transitions in urban transport congestion
• Evolution of road infrastructures in large urban areas
• On the stability of traffic breakup patterns in urban networks
• Information theoretic network approach to socioeconomic correlations
• From one-way streets to percolation on random mixed graphs
• Betweenness centrality in dense spatial networks
• Uncovering the role of spatial constraints in the differences and similarities between physical and virtual mobility
• Transitions in spatial networks
• Exploring the relationship between the spatial distribution of roads and universal pattern of travel-route efficiency in urban road networks
• A review of the structure of street networks
• Emergence of spatial transitions in urban congestion dynamics
• Linguistic evolution driven by network heterogeneity and the Turing mechanism
• Explosive dismantling of two-dimensional random lattices under betweenness centrality attacks
• Characterizing network circuity among heterogeneous urban amenities
• A link model approach to identify congestion hotspots
• A sampling-guided unsupervised learning method to capture percolation in complex networks
• Identifying Central Nodes in Multiplex Networks by Embracing Layer-Specific Heterogeneity via DomiRank
• superblockify: A Python Package for Automated Generation, Visualization, and Analysis of Potential Superblocks in Cities
• Vulnerability of Transport through Evolving Spatial Networks
• Predicting Urban Innovation from the Workforce Mobility Network in US