2017/02/17 by Elisabetta Bergamini, Bergamini, Elisabetta, Pierluigi Crescenzi +9 · 3 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph theory and applications #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1702.05284
openalex publication_date 2017/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 paper 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 ant 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.