Scaling up Electrical Closeness Centrality Computation
IEEE Transactions on Knowledge and Data Engineering · 2026-05 · 38 (5) · 3095-3108
DOI: 10.1109/tkde.2026.3670233 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Knowledge and Data Engineering, 2026-05. Verfasst von Meihao Liao und 3 weiteren Autor:innen. Die Arbeit nennt 55 Literaturangaben.
Abstract (Originalsprache)
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$ L † . To address this challenge, we propose novel solutions for approximating $L^\dagger$ L † by establishing a connection with the inverse of a Laplacian submatrix $L_{v}$ L v , which is obtained by removing the $v$ v -th row and column from the original Laplacian matrix $L$ L . A key advantage of this connection is that $L_{v}^{-1}$ L v - 1 admits various insightful combinatorial interpretations. Specifically, we present two novel interpretations of $L_{v}^{-1}$ 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.
Zitieren
APA
Liao, M., Li, R., Dai, Q., & Wang, G. (2026). Scaling up Electrical Closeness Centrality Computation. IEEE Transactions on Knowledge and Data Engineering, 38(5), 3095-3108. https://doi.org/10.1109/tkde.2026.3670233
Vancouver
Liao M, Li R, Dai Q, Wang G. Scaling up Electrical Closeness Centrality Computation. IEEE Transactions on Knowledge and Data Engineering. 2026;38(5):3095-3108. doi:10.1109/tkde.2026.3670233
BibTeX
@article{Liao2026,
author = {Liao, Meihao and Li, Rong-Hua and Dai, Qiangqiang and Wang, Guoren},
title = {Scaling up Electrical Closeness Centrality Computation},
journal = {IEEE Transactions on Knowledge and Data Engineering},
year = {2026},
volume = {38},
number = {5},
pages = {3095--3108},
doi = {10.1109/tkde.2026.3670233}
}
EUVIMED