Central loops in random planar graphs

Abstract

Random planar graphs appear in a variety of context and it is important for many different applications to be able to characterize their structure. Local quantities fail to give interesting information and it seems that path-related measures are able to convey relevant information about the organization of these structures. In particular, nodes with a large betweenness centrality (BC) display non-trivial patterns, such as central loops. We first discuss empirical results for different random planar graphs and we then propose a toy model which allows us to discuss the condition for the emergence of non-trivial patterns such as central loops. This toy model is made of a star network with $N_b$ branches of size $n$ and links of weight $1$, superimposed to a loop at distance $\ell$ from the center and with links of weight $w$. We estimate for this model the BC at the center and on the loop and we show that the loop can be more central than the origin if $w<w_c$ where the threshold of this transition scales as $w_c\sim n/N_b$. In this regime, there is an optimal position of the loop that scales as ${\ell }_{opt}\sim N_{b}w/4$. This simple model sheds some light on the organization of these random structures and allows us to discuss the effect of randomness on the centrality of loops. In particular, it suggests that the number and the spatial extension of radial branches are the crucial ingredients that control the existence of central loops.

arXiv commentRevised and augmented version, 13 pages, 12 figures

References in corpus (17)

• Spatial Networks
• The Network Analysis of Urban Streets: A Primal Approach
• 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
• Damage and fluctuations induce loops in optimal transport networks
• A Topological Pattern of Urban Street Networks: Universality and Peculiarity
• Networks and Cities: An Information Perspective
• Random planar graphs and the London street network
• Mathematics and Morphogenesis of the City: A Geometrical Approach
• Urban road networks -- Spatial networks with universal geometric features? A case study on Germany's largest cities
• Quantifying loopy network architectures
• Effect of congestion costs on shortest paths through complex networks
• Connected Spatial Networks over Random Points and a Route-Length Statistic
• Hierarchical ordering of reticular networks
• Interplay between function and structure in complex networks

Cited by in corpus (8)

• From the betweenness centrality in street networks to structural invariants in random planar graphs
• Incentive-driven transition to high ride-sharing adoption
• Forecasting failure locations in two-dimensional disordered lattices
• Evolution of road infrastructures in large urban areas
• Betweenness centrality in dense spatial networks
• Transitions in spatial networks
• A review of the structure of street networks
• Morphogenesis of complex networks: a reaction diffusion framework for spatial graphs