  Network centrality plays an important role in many applications. Central
nodes in social networks can be influential, driving opinions and spreading
news or rumors.In hyperlinked environments, such as the Web, where users
navigate via clicks, central content receives high traffic, becoming targets
for advertising campaigns. While there is an extensive amount of work on
centrality measures and their efficient computation, controlling nodes'
centrality via network updates is a more recent and challenging problem.
Performing minimal modifications to a network to achieve a desired property
falls under the umbrella of network design problems. This paper is focused on
improving the coverage centrality of a set of nodes, which is the number of
pairs of nodes that have a shortest path passing through the set, by adding
edges to the network. We prove strong inapproximability results and propose a
greedy algorithm for maximizing coverage centrality. To ensure scalability to
large networks, we also design an efficient sampling algorithm for the problem.
In addition to providing an extensive empirical evaluation of our algorithms,
we also show that, under some realistic constraints, the proposed solutions
achieve almost-optimal approximation for coverage centrality maximization.
