Towards Efficient Influence Maximization for Evolving Social Networks
Identifying the most influential individuals can provide invaluable help in developing and deploying effective viral marketing strategies.Previous studies mainly focus on designing efficient algorithms or heuristics to find top-K influential nodes on a given static social network.While,as a matter of fact,real-world social networks keep evolving over time and a recalculation upon the changed network inevitably leads to a long running time,significantly affecting the efficiency.In this paper,we observe from real-world traces that the evolution of social network follows the preferential attachment rule and the influential nodes are mainly selected from high-degree nodes.Such observations shed light on the design of IncInf,an incremental approach that can efficiently locate the top-K influential individuals in evolving social networks based on previous information instead of calculation from scratch.In particular,IncInf quantitatively analyzes the influence spread changes of nodes by localizing the impact of topology evolution to only local regions,and a pruning strategy is further proposed to effectively narrow the search space into nodes experiencing major increases or with high degrees.We carried out extensive experiments on real-world dynamic social networks including Facebook,NetHEPT,and Flickr.Experimental results demonstrate that,compared with the state-of-the-art static heuristic,IncInf achieves as much as 21× speedup in execution time while maintaining matching performance in terms of influence spread.
Xiaodong Liu Xiangke Liao Shanshan Li Bin Lin
National University of Defense Technology,Changsha 410073,China
国际会议
International Asia-Pacific Web Conference(第18届国际亚太互联网大会)
苏州
英文
232-244
2016-09-23（万方平台首次上网日期，不代表论文的发表时间）