Scaling up Electrical Closeness Centrality Computation

Electrical closeness centrality is a classical and robust graph centrality measure. However, existing algorithms for computing electrical closeness centrality are often computationally expensive for large graphs, as they require determining the diagonal elements of the pseudo-inverse of the graph Laplacian matrix, denoted as$L^\dagger$. To address this challenge, we propose novel solutions for approximating$L^\dagger$by establishing a connection with the inverse of a Laplacian submatrix$L_{v}$, which is obtained by removing the$v$-th row and column from the original Laplacian matrix$L$. A key advantage of this connection is that$L_{v}^{-1}$admits various insightful combinatorial interpretations. Specifically, we present two novel interpretations of$L_{v}^{-1}$based on spanning trees and loop-erased random walks, which facilitate the development of efficient sampling algorithms. Building upon these theoretical insights, we introduce two algorithms for efficiently approximating electrical closeness centrality. We extensively evaluate the performance of our algorithms on five real-world datasets. Experimental results demonstrate that our approaches significantly outperform state-of-the-art methods by several orders of magnitude in both running time and estimation accuracy.