Incremental Influence Maximization for Dynamic Social Networks  

作　　者：Yake Wang Jinghua Zhu Qian Ming 

机构地区：[1]School of Computer Science and Technology,Heilongjiang University, Harbin 150001, China [2]Key Laboratory of Database and Parallel Computing of Heilongjiang Province,Harbin, China

出　　处：《国际计算机前沿大会会议论文集》2017年第2期4-5,共2页International Conference of Pioneering Computer Scientists, Engineers and Educators（ICPCSEE）

摘　　要：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.

关 键 词：INFLUENCE MAXIMIZATION Dynamic SOCIAL network Linear THRESHOLD model PRUNING strategy 

分 类 号：C5[社会学]