IRIE: Scalable and Robust Influence Maximization in Social Networks - Jung, Kyomin; Heo, Wooram; Chen, Wei (In Proceedings of the 12th IEEE International Conference on Data Mining (ICDM'2012), Brussels, Belgium, December, 2012., 2012)
Inﬂuence maximization is the problem of selecting top k seed nodes in a social network to maximize their inﬂuence coverage under certain inﬂuence diffusion models. In this paper, we propose a novel algorithm IRIE that integrates the advantages of inﬂuence ranking (IR) and inﬂuence estimation (IE) methods for inﬂuence maximization in both the independent cascade (IC) model and its extension IC-N that incorporates negative opinion propagations. Through extensive experiments, we demonstrate that IRIE matches the inﬂuence coverage of other algorithms while scales much better than all other algorithms. Moreover IRIE is much more robust and stable than other algorithms both in running time and memory usage for various density of networks and cascade size. It runs up to two orders of magnitude faster than other state-of-the-art algorithms such as PMIA for large networks with tens of millions of nodes and edges, while using only a fraction of memory.