Efficient Algorithm for Maximizing Betweenness Centrality in Large Networks
Lists
Only you see this
Abstract
Betweenness centrality captures the importance of a vertex by quantifying the number of times it is traversed as part of the shortest path between other vertices. Betweenness centrality maximization is a fundamental task in network analysis with a wide range of applications. Specifically, given a network $G$ and a positive integer $k$, this problem aims to find a set with $k$ vertices that has the maximum betweenness centrality. Previous research has investigated different techniques for approximating betweenness centrality maximization with near-linear time complexity. Despite the theoretical guarantees that minimize the sample size, computing the betweenness centrality of all vertices can still be time-consuming, particularly for large graphs. In this paper, we propose a novel algorithm, BKBWC, for maximizing the betweenness centrality of a set of $k$ vertices in a network. Our method utilizes the bottom-k sketch to enable early termination when the seed set size meets $k$, significantly accelerating the algorithm while maintaining accuracy. We demonstrate the efficiency and accuracy of our method on 10 real-world datasets, showing that our algorithm achieves 30x speedup compared with the state-of-the-art approach HEDGE, while still producing results comparable to exact methods in terms of accuracy.
BibTeX
@inproceedings{zhang2023efficient,
author = {Lele Zhang and Yanping Wu and Jinghao Wang and Shiyuan Liu and Chen Chen and Xiaoyang Wang},
title = {{Efficient Algorithm for Maximizing Betweenness Centrality in Large Networks}},
booktitle = {HPCC/DSS/SmartCity/DependSys},
year = {2023},
url = {https://openreview.net/forum?id=Kn5K50xzRr},
}Loading related content...