Name
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 $I_v$ of a given node $v$ in a network with $n$ nodes and $m$ edges, by creating $k$ new edges incident to $v$. Since $I_v$ is the reciprocal of the sum of resistance distance $mathcal{R}_v$ between $v$ and all nodes, we alternatively consider the problem of minimizing $mathcal{R}_v$ 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-frac{1}{e}right)$ and $O(n^3)$ running time. To speed up the computation, we also present an algorithm to compute $left(1-frac{1}{e}-epsilonright)$-approximate resistance distance $mathcal{R}_v$ after iteratively adding $k$ edges, the running time of which is $widetilde{O} (mkepsilon^{-2})$ for any $epsilonu003e0$, where the $widetilde{O} (cdot)$ notation suppresses the ${rm poly} (log n)$ factors. We experimentally demonstrate the effectiveness and efficiency of our proposed algorithms. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.24963/ijcai.2018/491 | IJCAI |
DocType | Volume | Citations |
Conference | abs/1804.06540 | 0 |
PageRank | References | Authors |
0.34 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Liren Shan | 1 | 12 | 3.17 |
| Yuhao Yi | 2 | 22 | 6.91 |
| Zhongzhi Zhang | 3 | 85 | 22.02 |