Scalable Algorithms for Information Centrality Optimization via Global Edge Addition

Abstract

Information centrality is a powerful metric for quantifying node importance and has demonstrated practical value in a variety of real-world applications. Although existing studies have explored information centrality optimization via edge addition, they are restricted to a local setting, where candidate edges must be incident to the target node. Such restrictions fail to fully exploit the global structure of the network and often lead to suboptimal solutions under the same edge budget. In this work, we study the problem of global information centrality optimization, where candidate edges may connect any pair of currently non-adjacent nodes. This formulation significantly enlarges the search space and breaks the supermodularity property that underlies traditional greedy approaches, making the problem substantially more challenging. To address these challenges, we propose two scalable greedy algorithms based on gradient-guided edge selection. Our methods exploit geometric interpretations, dimensionality reduction techniques, and nearly-linear-time Laplacian solvers to efficiently approximate marginal gains and prune the candidate edge set. Extensive experiments on real-world networks demonstrate that our algorithms achieve optimization performance comparable to exact greedy strategies while substantially reducing computational time.