  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-\frac{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 $10^5$ edges in most cases in a matter of seconds or a
few minutes.
