A Fast Approximation Algorithm for the Top-$K$K Group Betweenness Centrality
IEEE Transactions on Knowledge and Data Engineering · 2026-06 · 38 (6) · 3335-3348
DOI: 10.1109/tkde.2026.3677004 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Knowledge and Data Engineering, 2026-06. Verfasst von Wenzheng Xu und 9 weiteren Autor:innen. Die Arbeit nennt 36 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Sichuan Science and Technology Program, Research Grants Council of the Hong Kong Special Administrative Region, China.
Abstract (Originalsprache)
Betweenness centrality is one of the key centrality measures in many applications including community detections in biological networks, vulnerability detections in communication networks, misinformation filtering in social networks, etc. The top- $K$ K group betweenness centrality problem is to find a group of $K$ K nodes from a network so that the total fraction of shortest paths that pass through the $K$ K nodes is maximized. Existing studies proposed randomized sampling algorithms for the problem. We notice that the existing studies ensured that, the maximum deviation of the estimated centrality of every group from its expectation is no greater than a small given threshold for all potential groups with no more than $K$ K nodes, thereby generating too many samples, as the number of such groups is prohibitively large. In contrast, in this paper we first devise a novel algorithm that enables to estimate the centrality of a tentative group adaptively, and the algorithm immediately stops once the centrality is large enough; otherwise, the algorithm uses more samples to find a better group. We then theoretically show that, even the proposed algorithm uses much less samples, it still can find a performance-guaranteed group with high probability. Experimental results with real-world networks demonstrate that the number of samples used by the proposed algorithm is up to 36 times smaller than the state-of-the-art, while the centrality of the group found by the algorithm is no more than 4.5% smaller than the latter.
Förderung
- National Natural Science Foundation of China
- Sichuan Science and Technology Program
- Research Grants Council of the Hong Kong Special Administrative Region, China
- Cooperative Program of Sichuan University and Yibin
- Cooperative Program of Sichuan University and Zigong
- Key R&D Program of Sichuan Province of China
Zitieren
APA
Xu, W., Li, J., Liang, W., Xu, Z., Peng, J., Zhou, P., Zhao, C., Yan, B., Jia, X., & Yu, J. X. (2026). A Fast Approximation Algorithm for the Top-$K$K Group Betweenness Centrality. IEEE Transactions on Knowledge and Data Engineering, 38(6), 3335-3348. https://doi.org/10.1109/tkde.2026.3677004
Vancouver
Xu W, Li J, Liang W, Xu Z, Peng J, Zhou P, et al. A Fast Approximation Algorithm for the Top-$K$K Group Betweenness Centrality. IEEE Transactions on Knowledge and Data Engineering. 2026;38(6):3335-3348. doi:10.1109/tkde.2026.3677004
BibTeX
@article{Xu2026,
author = {Xu, Wenzheng and Li, Jing and Liang, Weifa and Xu, Zichuan and Peng, Jian and Zhou, Pan and Zhao, Cheng and Yan, Binyu and Jia, Xiaohua and Yu, Jeffrey Xu},
title = {A Fast Approximation Algorithm for the Top-$K$K Group Betweenness Centrality},
journal = {IEEE Transactions on Knowledge and Data Engineering},
year = {2026},
volume = {38},
number = {6},
pages = {3335--3348},
doi = {10.1109/tkde.2026.3677004}
}
EUVIMED