2016/11/30 by Benjamin Lion, Marc Barthélemy, Marc Barthelemy · 1 citation
Biochemistry, Genetics and Molecular Biology · Engineering · Environmental Science · Mathematics · Physics and Astronomy · #Betweenness centrality #Centrality #Combinatorics #Computer science #Diffusion and Search Dynamics #Discrete mathematics #Extension (predicate logic) #Graph #Land Use and Ecosystem Services #Loop (graph theory) #Mathematical analysis #Mathematics #Path (computing) #Physics #Planar #Planar graph #Position (finance) #Random graph #Randomness #Star (game theory) #Statistical physics #Statistics #Urban Design and Spatial Analysis #cond-mat.stat-mech #physics.soc-ph
paper · pdf · doi:10.1103/physreve.95.042310
published as Physical Review E 95:042310 (2017) · Revised and augmented version, 13 pages, 12 figures
arxiv created 2017/03/27 · openalex publication_date 2017/04/14 · arxiv updated 2017/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Random planar graphs appear in a variety of contexts 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 nontrivial 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 nontrivial patterns such as central loops. This toy model is made of a star network with Nb branches of size n and links of weight 1, superimposed to a loop at distance ℓ 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<wc where the threshold of this transition scales as wc∼n/Nb. In this regime, there is an optimal position of the loop that scales as ℓopt∼Nbw/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.