🔬 physics

Betweenness centrality in dense spatial networks

This paper proposes a finite-density expansion for calculating betweenness centrality in spatial networks, demonstrating that the lowest non-trivial order captures path straightness and yields excellent agreement with numerical simulations across various graph types, thereby providing a robust framework for analyzing large spatial networks.

Original authors: Vincent Verbavatz, Marc Barthelemy

Published 2026-09-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vincent Verbavatz, Marc Barthelemy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the study of complex networks, scientists often look for ways to measure how important a specific point is within a vast system. Whether it is a city's street map, the internet, or a wireless communication network, some locations act as critical hubs where traffic naturally converges. To understand this, researchers use a concept called betweenness centrality. Imagine a network as a collection of points connected by lines, where information or goods travel along the shortest possible routes between any two points. Betweenness centrality counts how often a specific point lies on these shortest paths. If a point sits on many of these routes, it carries a heavy load; if it is bypassed by most travelers, its load is light. This measurement helps explain why certain intersections in a city become congested or why specific routers in a communication network might fail under pressure. While calculating this for simple, regular grids is straightforward, doing so for the messy, irregular networks found in the real world has historically been very difficult, often requiring computer simulations for every new case.

A team of physicists has now developed a new way to predict this traffic load for dense networks without needing to simulate every single path. They focused on networks built from points scattered randomly across a flat area, such as a city block or a wireless sensor field. In the theoretical limit where these points are packed infinitely close together, the shortest paths between them become perfectly straight lines, and the traffic load follows a universal rule that depends only on a point's distance from the center of the area. However, real-world networks are never infinitely dense; they have a finite number of points, causing the shortest paths to bend slightly as they navigate around gaps in the network. The researchers set out to understand exactly how these small bends affect the traffic load. They proposed a mathematical expansion that treats the finite density as a small correction to the perfect, infinite case. This correction term captures how much the paths deviate from being straight, a factor that changes depending on the specific rules used to connect the points.

The team tested their theory against several different types of networks constructed from random points. These included networks where points connect to their nearest neighbors, networks formed by triangulating the space, and others based on specific geometric rules like the Gabriel graph or the Delaunay triangulation. For most of these network types, the new analytical formula matched the results of massive computer simulations with remarkable accuracy. The agreement was so strong that the formula worked well even when the density of points was relatively low, corresponding to as few as six points per square unit in some cases. This suggests that the researchers have found a robust way to estimate traffic loads in large spatial networks simply by knowing the position of a point and the general density of the network, without needing to know the exact layout of every connection.

However, the study also revealed that this approach is not a one-size-fits-all solution. For two specific types of networks, the minimum spanning tree and the relative neighborhood graph, the standard formula did not hold up. In these cases, the assumption that the deviation of paths behaves in a uniform way across the network was incorrect. While the traffic load in these networks still eventually settles into the universal pattern as the density increases, the path to get there is different and more complex. The researchers noted that for these specific structures, the way shortest paths straighten out as points are added does not follow the same simple rule as the other networks. This indicates that while a general framework for understanding traffic in dense spatial networks is now within reach, the specific geometry of how points are connected still matters, particularly for certain tree-like structures.

The findings offer a powerful tool for understanding the hidden organization of spatial networks. By showing that the traffic load can be predicted from spatial coordinates alone for most dense networks, the work provides a bridge between abstract mathematical theory and the physical reality of cities and communication systems. It confirms that while the infinite density limit provides a universal baseline, the real-world behavior is shaped by the subtle, non-universal ways paths curve to avoid obstacles. The researchers observed that adding more points to a network generally reduces the average traffic load on any single point, as there are more alternative routes available. Yet, locally, the addition of new points can sometimes make a specific location more central, creating a complex dynamic where the overall trend and local behavior can pull in different directions. This nuanced view helps explain why some networks converge quickly to a predictable state while others take much longer, depending on the specific rules that govern how their connections are formed.

Technical Summary: Betweenness Centrality in Dense Spatial Networks

Problem Statement
Betweenness centrality (BC) is a fundamental metric for characterizing the importance of nodes in complex networks, particularly in identifying traffic bottlenecks and structural vulnerabilities in spatial networks (e.g., transportation, communication, and urban street networks). While BC is well-understood for simple topologies (grids, loops) and in the theoretical limit of infinite node density ( $\rho \to \infty$ ), its calculation for finite, dense spatial networks remains analytically challenging. In the infinite density limit on a bounded domain, shortest paths become straight lines, leading to a universal BC distribution dependent only on spatial coordinates. However, for large but finite densities, shortest paths deviate from straight lines, and it is unclear how these deviations affect the BC or whether the infinite density result remains a valid approximation. The paper addresses the need for an analytical framework to compute BC in quasi-dense spatial networks and to understand the non-universal corrections arising from finite density.

Methodology
The authors propose a perturbation expansion of the BC calculation around the infinite density limit. The study focuses on graphs constructed from $N$ points distributed randomly in a bounded domain $D$ (a disk or square) with density $\rho = N/V$ . Several specific graph construction rules are considered:

$k$ -Nearest Neighbors ( $k$ -NN)
Random Geometric Graph (RGG)
Minimum Spanning Tree (MST)
Delaunay Triangulation (DT)
Gabriel Graph (GG)
Relative Neighborhood Graph (RNG)

The core theoretical approach involves:

Continuous Approximation: Expressing the BC $g(\kappa)$ of a node $\kappa$ as an integral over the domain involving the probability $\chi_{ij}(\kappa)$ that $\kappa$ lies on the shortest path between nodes $i$ and $j$ .
Angular Deviation Parameterization: Defining an angular deviation $\epsilon_{ij}$ representing the deviation of the shortest path from the straight line connecting $i$ and $j$ relative to $\kappa$ .
Perturbation Expansion: Assuming that for certain graph families, the conditional probability $\chi_{ij}(\kappa|\epsilon_{ij})$ can be factorized into a geometric term (dependent on distances $r_i, r_j$ ) and a universal function $\chi(\epsilon)$ dependent only on the deviation angle.
Series Expansion: Expanding the function $\chi(\epsilon)$ around $\epsilon = 0$ (the infinite density limit) to the second order. The first-order term vanishes, leaving the second-order term as the leading non-trivial correction.
Numerical Validation: The analytical results are compared against numerical simulations using the Brandes algorithm, averaging over 5,000 realizations for various graph types and densities ( $N$ from 10 to 1000).

Key Contributions and Results

Analytical Expansion: The authors derive an explicit formula for the BC $g(\kappa)$ in the quasi-dense limit. The result consists of a universal term (independent of the graph structure, corresponding to the infinite density limit) and a correction term proportional to $\epsilon_0^2(\rho)$ , where $\epsilon_0(\rho)$ characterizes the typical angular deviation of shortest paths.
$g(\kappa) \propto I_0(\kappa) - \epsilon_0^2(\rho) I_2(\kappa, R)$
Here, $I_0$ and $I_2$ are integrals involving elliptic functions, and $\epsilon_0(\rho)$ is found to scale as a power law $\rho^{-\beta}$ with $\beta \approx 0.4$ .
Non-Universality of Corrections: The paper demonstrates that while the leading order (infinite density) BC is universal, the first non-trivial correction is non-universal. It depends on the specific graph construction because the deviation of shortest paths from straight lines varies between different graph types.
Empirical Agreement: For the Delaunay Triangulation (DT), Gabriel Graph (GG), $k$ -NN, and Random Geometric Graph (RGG), the analytical expansion shows excellent agreement with numerical simulations, even at relatively low densities (e.g., $\rho \approx 3$ to $6$ points per square unit). The GG and DT converge to the infinite density limit faster than the $k$ -NN.
Limitations and Exceptions: The proposed perturbation expansion fails for the Minimum Spanning Tree (MST) and Relative Neighborhood Graph (RNG). For these graphs, the assumption that the angular deviation distribution is independent of the specific node triplet $(i, j, \kappa)$ does not hold. However, the average BC for these graphs still converges to the infinite density limit, suggesting a different mechanism of convergence that requires further study.
2D Grid Case: The authors note that the infinite density approximation does not apply to regular 2D grids due to strong path degeneracy and non-straight shortest paths, though a separate simple geometric approximation (Eq. 6) works well for grids.

Significance
The paper provides a theoretical framework for understanding and computing betweenness centrality in large spatial networks where node density is high but finite. By extending the known infinite density results, the authors show that the BC can be approximated using only the spatial coordinates of a node, provided the graph belongs to specific families (DT, GG, RGG, $k$ -NN). The work highlights that the "straightness" of shortest paths is the critical factor governing the convergence to the universal limit. The results offer a practical tool for estimating traffic loads and identifying critical nodes in physical layer networks (such as wireless ad hoc networks) and urban planning without requiring full network simulation, provided the network density is sufficiently high. The paper modestly concludes that while the method works well for several standard spatial graphs, the behavior of MST and RNG networks remains an open question requiring further investigation into how shortest paths straighten with increasing density.

More like this