Weighted Betweenness and Algebraic Connectivity

Abstract

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.