On the Maximum Betweenness Improvement Problem

The betweenness is a well-known measure of centrality of a node in a network. We consider the problem of determining how much a node can increase its betweenness centrality by creating a limited amount of new edges incident to it. If the graph is directed, this problem does not admit a polynomial-time approximation scheme (unless P=NP) and a simple greedy approximation algorithm guarantees an almost tight approximation ratio [E. D. Demaine and M. Zadimoghaddam. Minimizing the diameter of a network using shortcut edges. In Proc. of the 12th Scandinavian Symp. and Work. on Algorithm Theory (SWAT), volume 6139 of LNCS, pages 420–431. Springer, 2010].In this paper we focus on the undirected graph case: we show that also in this case the problem does not admit a polynomial-time approximation scheme (unless P=NP). Moreover, we show that, differently from the directed case, the greedy algorithm can have an unbounded approximation ratio. In order to test the practical performance of the greedy algorithm, we experimentally measured its efficiency in term of ranking improvement, comparing it with another algorithm that simply adds edges to the nodes that have highest betweenness. Our experiments show that the greedy algorithm adds only few edges in order to increase the betweenness of a node and to reach the top positions in the ranking. Moreover, the greedy algorithm outperforms the second approach.