Elisabetta Bergamini
Pierluigi Crescenzi
Gianlorenzo D’angelo
Henning Meyerhenke
Lorenzo Severini
Yllka Velaj
2018
1
ACM Journal of Experimental Algorithmics, Volume 23 2018, Article No.: 1.5 pp 1–32
ACM
ournal of Experimental Algorithmics
10.1145/3166071
Betweenness is a well-known centrality measure that ranks the nodes according to their participation in the shortest paths of a network. In several scenarios, having a high betweenness can have a positive impact on the node itself. Hence, in this article, we consider the problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it.
In particular, we study the problem of maximizing the betweenness score of a given node—Maximum Betweenness Improvement (MBI)—and that of maximizing the ranking of a given node—Maximum Ranking Improvement (MRI). We show that MBI cannot be approximated in polynomial-time within a factor \((1−1/2e)\) and that MRI does not admit any polynomial-time constant factor approximation algorithm, both unless \(P=NP\). We then propose a simple greedy approximation algorithm for MBI with an almost tight approximation ratio and we test its performance on several real-world networks.
We experimentally show that our algorithm highly increases both the betweenness score and the ranking of a given node and that it outperforms several competitive baselines. To speed up the computation of our greedy algorithm, we also propose a new dynamic algorithm for updating the betweenness of one node after an edge insertion, which might be of independent interest. Using the dynamic algorithm, we are now able to compute an approximation of MBI on networks with up to 105 edges in most cases in a matter of seconds or a few minutes.
