Abstract
The problem of increasing the centrality of a network node arises in many practical applications. In this paper, we study the optimization problem of maximizing the information centrality Iv of a given node v in a network with n nodes and m edges, by creating k new edges incident to v. Since Iv is the reciprocal of the sum of resistance distance Rv between v and all nodes, we alternatively consider the problem of minimizing Rv by adding k new edges linked to v. We show that the objective function is monotone and supermodular. We provide a simple greedy algorithm with an approximation factor 1 ? 1e and O(n3 ) running time. To speed up the computation, wealso present an algorithm to compute 1 ? 1e ? -approximate resistance distance Rv after iteratively adding k edges, the running ?2 time of which is O(mk e ) for any > 0, where the O(·) e notation suppresses the poly(log n) factors. We experimentally demonstrate the effectiveness and efficiency of our proposed algorithms.