# Improving information centrality of a node in complex networks by adding edges

arXiv: https://arxiv.org/abs/1804.06540 · HTML: https://mlsanity.com/paper/1804.06540/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2018.

## Built on by (most cited first, 2 of 2)

- [A Fast Algorithm for Moderating Critical Nodes via Edge Removal](https://mlsanity.com/paper/2309.06392/) (2023)
- [Promoting Fairness in Information Access within Social Networks](https://mlsanity.com/paper/2512.14711/) (2025)

## Abstract (arXiv)

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 left(1-frac1eright) and O(n3) running time. To speed up the computation, we also present an algorithm to compute left(1-frac1e-εright)-approximate resistance distance Rv after iteratively adding k edges, the running time of which is widetildeO (mkε-2) for any ε>0, where the widetildeO (·) notation suppresses the rm poly (log n) factors. We experimentally demonstrate the effectiveness and efficiency of our proposed algorithms.