  We propose a generalized framework for influence maximization in large-scale,
time evolving networks. Many real-life influence graphs such as social
networks, telephone networks, and IP traffic data exhibit dynamic
characteristics, e.g., the underlying structure and communication patterns
evolve with time. Correspondingly, we develop a dynamic framework for the
influence maximization problem, where we perform effective local updates to
quickly adjust the top-k influencers, as the structure and communication
patterns in the network change. We design a novel N-Family approach (N=1, 2, 3,
...) based on the maximum influence arborescence (MIA) propagation model with
approximation guarantee of (1-1/e). We then develop heuristic algorithms by
extending the N-Family approach to other information propagation models (e.g.,
independent cascade, linear threshold) and influence maximization algorithms
(e.g., CELF, reverse reachable sketch). Based on a detailed empirical analysis
over several real-world, dynamic, and large-scale networks, we find that our
proposed solution, N-Family improves the updating time of the top-k influencers
by 1-2 orders of magnitude, compared to state-of-the-art algorithms, while
ensuring similar memory usage and influence spreads.
