Betweenness centrality in dense spatial networks

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 $N$ 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 nontrivial order and show that it encodes how straight are shortest paths and is therefore nonuniversal 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.

Figure 1

(a) Approximation for computing the BC for the 2D grid: the BC at node $(i,0)$ is proportional to the product of shaded areas (up to a factor two accounting for the white squares). (b) Comparison of the approximation of Eq. (5) to the analytical formula of Eq. (4) computed numerically for $L=15$. (c) Relative error of the approximation of Eq. (6) on the square grid.

Figure 2

Sketch of the system considered and notations. The origin of the polar system is $\kappa$ and the nodes $i$ and $j$ have the coordinates $(r_i,{\theta }_i)$ and $(r_j,{\theta }_j)$ in this system. The deviation of the two segments $\left(i\kappa \right)$ and $(\kappa ,j)$ from the straight line is characterized by the angle ${\varepsilon }_{ij}={\theta }_i-{\theta }_j+\pi$.

Figure 3

Writing $\chi \left(\epsilon \right)={\epsilon }_0\left(\rho \right)e^{-\epsilon /{\epsilon }_0\left(\rho \right)}$, we show that ${\epsilon }_0$ is a smooth decreasing function of the density $\rho$, validating the shape of $\chi \left(\epsilon \right)$ for $k$-NN, RGG, DT, and GG graphs (the vertical error bars correspond to the dispersion). The graph suggests a power law relation of the form ${\epsilon }_0\left(\rho \right)\simeq A{\rho }^{-\beta }$ with $\beta \simeq 0.5\pm 0.1$. We note that the exponent is not the exact same for all graphs, nor is the prefactor, thus making some types of graphs converging faster toward the dense regime than others.

Figure 4

Comparison of the expansion of Eq. (35) with the numerical result for the DT. The quality of the approximation increases with the density but is insightful at surprisingly low densities (6 points per square unit is less than 20 points in the disk). The number of points is $N=\rho \pi$.

Figure 5

Comparison of the expansion of Eq. (35) with the numerical result for the $k$-NN. The quality of the approximation increases with the density but it is already very good for a density $\rho =9$ or larger. The number of points is $N=\rho \pi$.

Figure 6

Comparison of the expansion of Eq. (35) with the numerical result for the RGG. The convergence to the infinite density limit is faster than for other graphs and the approximation is very good for densities as low as $\rho =9$. The number of points is $N=\rho \pi$.

Figure 7

Comparison of the expansion of Eq. (35) with the numerical result for the GG. The convergence to the infinite density limit is much faster than for other graphs and the approximation is very good for densities as low as $\rho =3$. The number of points is $N=\rho \pi$.

Figure 8

Comparison of the expansion of Eq. (35) with the numerical result for the MST. The average BC converges toward the dense regime limit but the second-order approximation we used is not valid in this specific case.

Figure 9

Comparison of the speed of convergence of $k$-NN graphs toward the infinite density limit for different values of $k$: $k=5$ (top line), $k=15$ (middle line), and $k=25$ (bottom line). The correction differs as the empirical fit of the prefactor $A$ in Eq. (21) depends on the specific value of $k$.

Figure 10

Comparison of the speed of convergence of RGG graphs toward the infinite density limit for different values of the radius cutoff $r$.

Figure 11

Comparison of the quality of the correction as a function of point density for the different families of graphs. The quality is defined as the area between theoretical approximations (the infinite density limit $g_{\infty }^{*}$ and our expansion $g_{\text{th}}^{*}$) and the simulated (average) curves. The quality of both our approximation and the infinite density limit increases as the density does. As expected, the quality of the correction is better than the infinite density limit but the difference vanishes as the density increases.

Figure 12

Comparison of the exact numerical result for the 2D lattice, the approximation Eq. (6), and the result obtained for the infinite density Eq. (30). We observe here that the infinite density result does not apply to this case.

Figure 13

On average, the BC decreases when constructing a Gabriel graph from a Delaunay triangulation. This results from the fact that the GG are subgraphs of DT. We note that the BC change is negative for all positions of $\kappa$ except close to the edge of the disk, due to finite-size effects. These effects get more localized when increasing the density of points.