Source-linked AI summary
From the betweenness centrality in street networks to structural invariants in random planar graphs
Alec Kirkley, Hugo Barbosa, Marc Barthelemy, Gourab Ghoshal
TL;DR
The paper examines whether betweenness centrality distributions remain stable despite local topological and edge-weight changes in planar networks. Using planar-network analyses and tree-based approximations, it finds that planarity is the dominant factor shaping an invariant distribution.
Problem
The paper addresses whether betweenness centrality remains stable despite its potential sensitivity to local topological changes.
Method
The paper analyzes planar-network structure and approximates difficult cases using k-ary tree models.
Results
Planarity appears to dominate the betweenness-centrality distribution, while topology and edge weights have comparatively limited effects.
Takeaways & Limitations
The results support the remarkable invariance of betweenness-centrality distributions in random planar graphs.
Takeaways & Limitations
Geospatial variations alone do not explain the distribution’s form, scaling with N, or bimodality.
Abstract
from arXiv · showhide
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.
Effect of local topology
Rewiring local neighborhoods while preserving node positions, edge count, and planarity changes the lower BC distribution but leaves its peak location and tail largely unchanged. The same behavior appears across random graphs based on multiple cities.
- Effect of local topology: Local topology rewiring produced differences in the lower range of the BC distribution while minimally changing the peak location and tail.The rewiring changed node degrees and neighbors while maintaining planarity and matched the baseline edge count.
- Effect of local topology: The same behavior was observed in random graphs generated using several other cities as baselines.These graphs likewise showed limited change in the peak location and distribution tail despite local neighborhood rewiring.
Effect of edge weights
The BC distribution is largely insensitive to spatial edge-weight changes: its tails remain similar and peak positions unchanged. Randomly reshuffling weights causes only minor peak shifts and a moderately heavier tail, with little dependence on the weight distribution’s specific form.
- Spatial edge weights: Spatial edge-weight perturbations leave the BC distribution’s tails similar and its peak positions unchanged.The effect was marginally stronger than edge rewiring but remained within error bars.
- Spatial edge weights: The distribution of spatial edge-weights has negligible effect on the BC distribution across cities and node densities.The procedure varied spatial arrangements and network realizations while matching the observed number of roads.
- Non-spatial edge weights: Randomly reshuffling edge weights produces minor peak shifts and a moderately heavier tail, without drastic distributional modifications.Weights were reassigned while preserving the network’s degree sequence and interpreted as costs such as speed limits, travel demand, or road capacity.
- Non-spatial edge weights: Exponential, power-law, and log-normal edge-weight distributions produce identical results, indicating little-to-no dependence on the weights’ specific nature.This conclusion applies to both spatial and non-spatial weights.
Relaxing planarity
Relaxing planarity produces a markedly different betweenness-centrality distribution, showing that planarity dominates over topology and edge weights. A Cayley-tree approximation explains the high-BC scaling and indicates that high-BC street nodes lie on an underlying spanning-tree structure.
- Relaxing planarity: The non-spatial configuration-model network has a markedly different BC curve, indicating that planarity dominates the distribution while topology and edge weights play negligible roles.The comparison fixes N and the degree sequence while assigning weights from Phoenix’s distance distribution.
- Cayley tree approximation: For a Cayley tree, node betweenness scales as gB(v|k, l) ∼O(NkL−l), yielding a node-betweenness scaling exponent α = 1.This tree approximation assumes a fixed branching ratio and equal leaf depth.
- Cayley tree approximation: The Cayley-tree result explains both the empirical BC tail’s form and its scaling with N.The calculation is consistent with previous calculations of link betweenness.
- Cayley tree approximation: High-BC nodes in city streets lie on an underlying spanning tree, concentrating the majority of flow around that tree.Street-network analogs of high-betweenness tree nodes include nodes adjacent to dead-ends.
- Relaxing planarity: In planar graphs, edge-weight distributions have little-to-no effect on BC, unlike weighted non-planar random graphs where this holds only for specific weight families.The contrast further supports planarity as the dominant structural constraint.
A simple model with variable density
Increasing edge density in random planar graphs creates loops that bypass high-betweenness nodes, producing a bimodal distribution that progressively smooths toward the Delaunay-triangulation limit. The distribution retains a high-BC tree backbone and a low-BC loop regime, with the range expanding from [N, N 2/2] for the MST to [1, N 2] for the DT.
- Density and loops: Loops created by adding edges bypass high-BC nodes, inducing a low-BC regime and sharper tail cutoffs consistent with street-network observations.Alternate local paths reduce the contribution of previously central MST nodes to shortest paths.
- Density and loops: The edge-density control parameter ρe ranges from approximately 1/3 for the MST to 1 for the Delaunay triangulation and captures edge-to-node ratio.For maximally planar graphs, eDT ≈3N, linking ρe to the average degree of street intersections.
- Random planar graph model: For N = 104, the MST BC distribution peaks at N and spans approximately [104, 108], closely following the Cayley-tree calculation.The MST has no loops, so its high-BC structure follows the underlying tree regime.
- Random planar graph model: Adding loops produces a bimodal BC distribution: a high-BC MST backbone coexists with low-BC loop nodes created by alternate paths.The distribution remains peaked at N while the tail maintains its shape during the initial transition.
- Random planar graph model: As ρe increases toward the DT, the distribution becomes more homogeneous while remaining peaked around N and broadening from [N, N 2/2] to [1, N 2].Loop decoration creates arbitrarily low betweenness values through multiple alternate paths, smoothing the distribution.
Spatial distribution of high BC nodes: characterization
High-BC nodes shift from spatially uncorrelated, tree-like patterns in sparse planar networks to clustered, isotropic patterns near the barycenter as edge density increases. This transition occurs around ρe ≈0.4, where loops emerge and spatial dependence becomes pronounced.
- Spatial distribution of high BC nodes: characterization: High-BC nodes transition from spanning, tree-like patterns without apparent spatial correlation to clustered groups near the barycenter as edge density increases.The study characterizes this shift as a transition between a topological regime and a spatial regime.
- Spatial distribution of high BC nodes: characterization: ⟨Cθ⟩ decreases by approximately a factor of two from the MST to the DT, confirming robust spatial clustering of high-BC nodes.This result holds for thresholds θ = 90, 95, and 97.
- Spatial distribution of high BC nodes: characterization: At ρe ≈0.4, equivalently ⟨k⟩≈2, the detour factor drops rapidly as the network transitions from a tree-like to a loop-like region.Loops lower detours and produce paths that are increasingly straight geometrically.
- Spatial distribution of high BC nodes: characterization: For ρe > 0.4, average BC decreases monotonically with distance from the barycenter, whereas low-density networks show no distance dependence.The high-density curves converge toward the form calculated for maximally dense random geometric graphs.
- Spatial distribution of high BC nodes: characterization: In representative cities, Santiago exhibits a tree-like anisotropic pattern, while Shenyang shows relatively symmetric clustering of high-BC nodes around the city center.Paris and Tokyo occupy an intermediate regime with lattice-like structures and loops spanning the cities.
Beyond static structure: Temporal evolution of BC in cities
Across five Paris street-network snapshots from 1790–1999, the spatial organization of high-BC nodes changed sharply after the Haussmann transformation, while the rescaled BC distribution remained identical. The intervention redistributed structural load and altered congestion patterns without eliminating the centrally located high-BC backbone.
- Spatial persistence: High-BC nodes remained near the city center relative to the region’s spatial extent, even after the radial-to-ring transition.The high-BC backbone continued to lie closer to the center than the city periphery.
- Distributional invariance: Despite the structural changes, the rescaled BC distribution, ˜gB, was identical across all 5 snapshots.This indicates that local topological variations had only a marginal effect on the global BC distribution.
- Intervention effects: The Haussmann transformation redistributed load to a different part of the network rather than eliminating structural congestion.It improved navigability and decongested the center, but the high-BC backbone remained centrally concentrated.