Improving information centrality of a node in complex networks by adding edges
| Autor: | Zhongzhi Zhang, Liren Shan, Yuhao Yi |
|---|---|
| Předmět: |
Social and Information Networks (cs.SI)
FOS: Computer and information sciences Optimization problem Resistance distance Computation Computer Science - Social and Information Networks Binary logarithm Combinatorics Monotone polygon Simple (abstract algebra) Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) Greedy algorithm Centrality Mathematics |
| Zdroj: | Scopus-Elsevier IJCAI |
| Popis: | 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}-\epsilon\right)$-approximate resistance distance $\mathcal{R}_v$ after iteratively adding $k$ edges, the running time of which is $\widetilde{O} (mk\epsilon^{-2})$ for any $\epsilon>0$, where the $\widetilde{O} (\cdot)$ notation suppresses the ${\rm poly} (\log n)$ factors. We experimentally demonstrate the effectiveness and efficiency of our proposed algorithms. Comment: 7 pages, 2 figures, ijcai-2018 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|