  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 21X speedup in
execution time while maintaining matching performance in terms of influence
spread.
