期刊
KNOWLEDGE AND INFORMATION SYSTEMS
卷 30, 期 3, 页码 613-635出版社
SPRINGER LONDON LTD
DOI: 10.1007/s10115-011-0396-2
关键词
Information diffusion; SIS model; Influence maximization; Pruning method; Burnout method
资金
- Asian Office of Aerospace Research and Development
- Air Force Office of Scientific Research
- US Air Force Research Laboratory [AOARD-10-4053]
- JSPS [20500147]
We address the problem of discovering the influential nodes in a social network under the susceptible/infected/susceptible model that allows multiple activation of the same node, by defining two influence maximization problems: final-time and integral-time. We solve this problem by constructing a layered graph from the original network with each layer added on top as the time proceeds and applying the bond percolation with two effective control strategies: pruning and burnout. We experimentally demonstrate that the proposed method gives much better solutions than the conventional methods that are based solely on the notion of centrality using two real-world networks. The pruning is most effective when searching for a single influential node, but burnout is more powerful in searching for multiple nodes which together are influential. We further show that the computational complexity is much smaller than the naive probabilistic simulation both by theory and experiment. The influential nodes discovered are substantially different from those identified by the centrality measures. We further note that the solutions of the two optimization problems are also substantially different, indicating the importance of distinguishing these two problem characteristics and using the right objective function that best suits the task in hand.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据