Extracting Influential Nodes for Information Diffusion on a Social Network
Extracting Influential Nodes for Information Diffusion on a Social Network
复制标题
DOI：
--
复制
发表时间：
2007-07
期刊：
影响因子：
--
通讯作者：
M. Kimura;Kazumi Saito;R. Nakano
中科院分区：
文献类型：
--
作者：
M. Kimura;Kazumi Saito;R. Nakano
我们考虑了两个广泛使用的基本随机扩散模型在大规模社会网络上寻找最有影响力节点的组合优化问题。结果表明，采用自然的贪婪策略可以很好地近似求解该优化问题。然而，贪婪算法下的传统方法需要大量的计算量，因为它通过多次模拟每个模型的随机过程来估计受一组节点影响的期望节点数的边际收益。本文基于键渗流和图论提出了一种有效估计所有这些量的方法，并将其应用于贪婪算法下的优化问题的近似求解。使用包括博客网络在内的真实世界的大规模网络，实验证明，该方法的性能优于传统方法，并实现了计算代价的大幅降低。
We consider the combinatorial optimization problem of finding the most influential nodes on a large-scale social network for two widely-used fundamental stochastic diffusion models. It was shown that a natural greedy strategy can give a good approximate solution to this optimization problem. However, a conventional method under the greedy algorithm needs a large amount of computation, since it estimates the marginal gains for the expected number of nodes influenced by a set of nodes by simulating the random process of each model many times. In this paper, we propose a method of efficiently estimating all those quantities on the basis of bond percolation and graph theory, and apply it to approximately solving the optimization problem under the greedy algorithm. Using real-world large-scale networks including blog networks, we experimentally demonstrate that the proposed method can outperform the conventional method, and achieve a large reduction in computational cost.