Weighted Betweenness and Algebraic Connectivity

Weighted Betweenness and Algebraic Connectivity

Martin-Hernandez, J.
Li, Z.
Van Mieghem, P.

Electrical Engineering, Mathematics and Computer Science

Network Architectures & Services (NAS)

2014-02-21

One of the better studied topology metrics of complex networks is the second smallest eigenvalue of the Laplacian matrix of a network’s graph, referred to as the algebraic connectivity mN-1. This spectral metric plays a decisive role in synchronization of coupled oscillators, network robustness, consensus problems, belief propagation, graph partitioning, and distributed filtering in sensor networks. However, computing the graph spectra is computationally slow and its convergence greatly depends on the topology, thus a number of lower bounds have been proposed over the years in order to find good approximations. To date, the closest bound is the one proposed by Rad et al. [21] in 2009. The current paper proposes new approximations for the algebraic connectivity based on three variations of the betweenness centrality, a popular centrality score often used in social studies to characterize the importance of a node or link within a network. Based on numerical and a partly analytic analysis, we show that our approximations provide accurate lower bounds for the algebraic connectivity for a wide range of graphs, including random, power-law, small-world, and lattice graphs. In particular, we numerically show that the average weighted Brandes betweenness can be treated as a lower bound for large enough networks, which greatly improves state-of-the-art bounds.

algebraic connectivity
betweenness
lower bound

http://resolver.tudelft.nl/uuid:e9e9ccdd-49cf-4bf9-abe0-4d8e694e3d6a

https://doi.org/10.1093/comnet/cnu007

Oxford University Press

2051-1329

Journal of Complex Networks (2014) Post-print version

Institutional Repository

journal article

(c) 2014 the authors