Coverage Centrality Maximization in Undirected Networks

Gianlorenzo D'Angelo, Martin Olsen, Lorenzo Severini

In network analysis, coverage centrality is a vital metric that quantifies the importance of a node based on how many shortest paths between other node pairs pass through it. Increasing a node's centrality is a common objective in various domains, from enhancing a person's influence in social networks to improving the efficiency of transportation hubs. This paper, presented at AAAI-19, investigates the Maximum Coverage Improvement (MCI) problem: adding a budget of $k$ edges incident to a target node $v$ to maximize its coverage centrality in an undirected graph.

The Challenge of Non-Submodularity

While the MCI problem is relatively straightforward in directed graphs due to the submodular nature of the objective function, undirected networks present a significant algorithmic challenge. In directed graphs, the benefit of adding an edge follows the law of diminishing returns. However, in undirected graphs, this property breaks down due to "synergistic effects" between edges.

Illustration of edge synergy in undirected networks.

As illustrated in Figure 1, adding a single edge might yield zero improvement in coverage centrality, while adding a specific pair of edges can suddenly cover a large number of shortest paths. For instance, if node $v$ connects to both $a_3$ and $b_3$, it may become a bridge for all shortest paths between the $a$-cluster and the $b$-cluster. This non-submodularity makes the problem NP-hard and difficult to approximate. The authors demonstrate that MCI is closely related to the "Densest-$k$-subgraph" problem, implying that it is unlikely to have a high-quality approximation ratio in the worst case.

Proposed Algorithmic Solutions

To address the complexities of undirected networks, the authors propose two specialized greedy procedures:

  1. GREEDY1 (Look-ahead Greedy): Instead of picking one edge at a time, this algorithm selects sets of $t$ edges simultaneously. By looking ahead, it can capture the synergistic benefits that a standard greedy approach would miss.
  2. GREEDY2 (Reduction to MCP): This approach reduces MCI to the "Maximum Coverage with Pairs" (MCP) problem. It distinguishes between "single coverage" (pairs reached via one new edge) and "double coverage" (pairs reached via two new edges), managing them separately to optimize the selection.

By combining these strategies into a hybrid algorithm, the authors establish a theoretical approximation guarantee of $\Omega(1/\sqrt{n})$.

Experimental Evaluation

The researchers evaluated their algorithms on both synthetic models (Barabasi-Albert and Configuration Model) and real-world social networks (e.g., Zachary’s Karate Club, Haggle contact network). To establish a "gold standard," they developed an Integer Programming (IP) formulation to compute the exact mathematical optimum for smaller networks.

Performance of greedy algorithms vs. mathematical optimum in a Barabasi-Albert (BA) network.

The experimental results, shown in Figure 4 for a Barabasi-Albert network, reveal that the proposed heuristics perform remarkably well in practice. GREEDY1 (with $t=2$ or $3$) consistently achieved an approximation ratio exceeding 0.97 relative to the true optimum. While GREEDY1 is highly accurate, its computational complexity increases with the look-ahead parameter $t$. In contrast, GREEDY2 offers better scalability for larger edge budgets ($k$), making it suitable for more extensive network interventions.

Conclusion

This research highlights the fundamental difference between directed and undirected networks in the context of centrality maximization. By identifying the "synergy trap" of non-submodularity and proposing robust greedy heuristics, the authors provide a practical toolkit for network administrators. Future work may explore more complex scenarios, such as adding edges that are not incident to the target node or finding tighter theoretical bounds for specific graph topologies like power-law networks.

Summary updated

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 $Ω(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.
BibTeX
@inproceedings{dangelo2019coverage,
  author = {Gianlorenzo D'Angelo and Martin Olsen and Lorenzo Severini},
  title = {{Coverage Centrality Maximization in Undirected Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.3301501},
}
Figure