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.
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:
- 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.
- 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.
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