Betweenness centrality in dense spatial networks
arXiv:2109.09553 · doi:10.1103/PhysRevE.105.054303
Abstract
The betweenness centrality (BC) is an important quantity for understanding the structure of complex large networks. However, its calculation is in general difficult and known in simple cases only. In particular, the BC has been exactly computed for graphs constructed over a set of points in the infinite density limit, displaying a universal behavior. We reconsider this calculation and propose an expansion for large and finite densities. We compute the lowest non-trivial order and show that it encodes how straight are shortest paths and is therefore non-universal and depends on the graph considered. We compare our analytical result to numerical simulations obtained for various graphs such as the minimum spanning tree, the nearest neighbor graph, the relative neighborhood graph, the random geometric graph, the Gabriel graph, or the Delaunay triangulation. We show that in most cases the agreement with our analytical result is excellent even for densities of points that are relatively low. This method and our results provide a framework for understanding and computing this important quantity in large spatial networks.
arXiv comment10 pages, 10 figures
References in corpus (15)
- Centrality Measures in Spatial Networks of Urban Streets
- Betweenness Centrality in Large Complex Networks
- Scaling laws in the spatial structure of urban road networks
- Congestion and centrality in traffic flow on complex networks
- From the betweenness centrality in street networks to structural invariants in random planar graphs
- Transport in weighted networks: Partition into superhighways and roads
- The Large Scale Curvature of Networks
- Euclidean versus hyperbolic congestion in idealized versus experimental networks
- Connected Spatial Networks over Random Points and a Route-Length Statistic
- Centrality scaling in large networks
- Impact of boundaries on fully connected random geometric networks
- Elementary processes governing the evolution of road networks
- The shape of shortest paths in random spatial networks
- Multiple abrupt phase transitions in urban transport congestion
- Central loops in random planar graphs