Paper Info
Title
On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social Networks
Abstract
Influence maximization problem aims to identify the most influential individuals so as to help in developing effective viral marketing strategies over social networks. Previous studies mainly focus on designing efficient algorithms or heuristics on a static social network. As amatter of fact, real-world social networks keep evolving over time and a recalculation upon the changed network inevitably leads to a long running time. In this paper, we propose an incremental approach, IncInf, which 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 narrow the search space into nodes experiencing major increases or with high degrees. To evaluate the efficiency and effectiveness, we carried out extensive experiments on real-world dynamic social networks: Facebook, NetHEPT, and Flickr. Experimental results demonstrate that, compared with the state-of-the-art static algorithm, IncInf achieves remarkable speedup in execution time while maintaining matching performance in terms of influence spread.
Year
DOI
Venue
2015
10.1155/2017/5049836
COMPLEXITY
Field
DocType
Volume
Viral marketing,Social network,Heuristics,Artificial intelligence,Execution time,Machine learning,Mathematics,Maximization,Speedup
Journal
2017
ISSN
Citations 
PageRank 
1076-2787
12
0.52
References 
Authors
19
9
Name
Order
Citations
PageRank
Xiaodong Liu15720.69
Xiangke Liao262274.79
Shanshan Li329553.11
Si Zheng4141.21
Bin Lin5273.21
JingYing Zhang6262.64
Lisong Shao7120.52
Chenlin Huang8488.83
Liquan Xiao910615.43