EUVIMEDEUVIMED entdecken
Crossref

Scaling up Electrical Closeness Centrality Computation

Meihao Liao, Rong-Hua Li, Qiangqiang Dai, Guoren Wang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →