Incremental Influence Maximization for Dynamic Social Networks

• 作者: Jinghua Zhu Qian Ming Yake Wang
• 来源期刊: 国际计算机前沿大会会议论文集
• 学科: 社会科学
• 关键词: INFLUENCE MAXIMIZATION Dynamic SOCIAL network Linear THRESHOLD model PRUNING strategy
• 年，卷（期）: 2017,（2）
• 页码范围: 4-5
• 页数: 2页
• 分类号: C5

摘要

Influence maximization is one fundamental and important problem to identify a set of most influential individuals to develop effective viral marketing strategies in social network. Most existing studies mainly focus on designing efficient algorithms or heuristics to find Top-K influential individuals for static network. However, when the network is evolving over time, the static algorithms have to be re-executed which will incur tremendous execution time. In this paper, an incremental algorithm DIM is proposed which can efficiently identify the Top-K influential individuals in dynamic social network based on the previous information instead of calculating from scratch. DIM is designed for Linear Threshold Model and it consists of two phases: initial seeding and seeds updating. In order to further reduce the running time, two pruning strategies are designed for the seeds updating phase. We carried out extensive experiments on real dynamic social network and the experimental results demonstrate that our algorithms could achieve good performance in terms of influence spread and significantly outperform those traditional static algorithms with respect to running time.