Incremental Influence Maximization for Dynamic Social Networks

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.