Extracting influential nodes on a social network for information diffusion
Extracting influential nodes on a social network for information diffusion
复制标题
DOI：
10.1007/s10618-009-0150-5
复制
发表时间：
2010-01-10
影响因子：
4.8
通讯作者：
Motoda, Hiroshi
中科院分区：
文献类型：
--
作者：
Kimura, Masahiro;Saito, Kazumi;Motoda, Hiroshi
我们解决了组合优化问题，找到最有影响力的节点上的两个广泛使用的基本随机扩散模型的大规模社会网络。过去的研究表明，贪婪策略可以给出一个很好的近似解的问题。然而，传统的贪婪方法面临计算问题。基于键渗流理论和图论，提出了一种在贪婪算法下有效地找到问题的近似解的方法，并将该方法与传统方法在计算复杂度方面进行了比较，从理论上评估了其有效性.结果表明，该方法有望实现大幅度降低计算成本。我们进一步的实验证明，该方法是更有效的比传统的方法使用大规模的真实世界的网络，包括博客网络。
We address the combinatorial optimization problem of finding the most influential nodes on a large-scale social network for two widely-used fundamental stochastic diffusion models. The past study showed that a greedy strategy can give a good approximate solution to the problem. However, a conventional greedy method faces a computational problem. We propose a method of efficiently finding a good approximate solution to the problem under the greedy algorithm on the basis of bond percolation and graph theory, and compare the proposed method with the conventional method in terms of computational complexity in order to theoretically evaluate its effectiveness. The results show that the proposed method is expected to achieve a great reduction in computational cost. We further experimentally demonstrate that the proposed method is much more efficient than the conventional method using large-scale real-world networks including blog networks.