Title: Coverage Centrality Maximization in Undirected Networks,
Abstract: Centrality metrics are among the main tools in social network analysis. Being
central for a user of a network leads to several benefits to the user: central
users are highly influential and play key roles within the network. Therefore,
the optimization problem of increasing the centrality of a network user
recently received considerable attention. Given a network and a target user
$v$, the centrality maximization problem consists in creating $k$ new links
incident to $v$ in such a way that the centrality of $v$ is maximized,
according to some centrality metric. Most of the algorithms proposed in the
literature are based on showing that a given centrality metric is monotone and
submodular with respect to link addition. However, this property does not hold
for several shortest-path based centrality metrics if the links are undirected.
In this paper we study the centrality maximization problem in undirected
networks for one of the most important shortest-path based centrality measures,
the coverage centrality. We provide several hardness and approximation results.
We first show that the problem cannot be approximated within a factor greater
than $1-1/e$, unless $P=NP$, and, under the stronger gap-ETH hypothesis, the
problem cannot be approximated within a factor better than $1/n^{o(1)}$, where
$n$ is the number of users. We then propose two greedy approximation
algorithms, and show that, by suitably combining them, we can guarantee an
approximation factor of $\Omega(1/\sqrt{n})$. We experimentally compare the
solutions provided by our approximation algorithm with optimal solutions
computed by means of an exact IP formulation. We show that our algorithm
produces solutions that are very close to the optimum.