Improving Information Centrality of a Node in Complex Networks by Adding Edges

Improving Information Centrality of a Node in Complex Networks by Adding Edges

Liren Shan, Yuhao Yi, Zhongzhi Zhang

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 3535-3541. https://doi.org/10.24963/ijcai.2018/491

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 − 1/e) and O(n^3) running time. To speed up the computation, we also present an algorithm to compute (1 − 1/e − epsilon) approximate resistance distance Rv after iteratively adding k edges, the running time of which is Otilde(mk*epsilon^−2) for any epsilon > 0, where the Otilde(·) notation suppresses the poly(log n) factors. We experimentally demonstrate the effectiveness and efficiency of our proposed algorithms.
Keywords:
Machine Learning: Data Mining
Constraints and SAT: Constraint Optimisation
Multidisciplinary Topics and Applications: Social Sciences
Machine Learning Applications: Networks