IRIE: Scalable and Robust Influence Maximization in Social Networks

By Kyomin Jung, Wooram Heo. 2012 IEEE 12th International Conference on Data Mining, 2011

459 citations recorded by the source corpus.

Influence maximization is the problem of selecting top k seed nodes in a social network to maximize their influence coverage under certain influence diffusion models. In this paper, we propose a novel algorithm IRIE that integrates the advantages of influence ranking (IR) and influence estimation (IE) methods for influence 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 influence 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.

Subfields: Communication, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/04aec04c71e0552c17296a2f5cb0680d4731ffff

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Communication

In Statistical and Nonlinear Physics

Citations in the corpus

Influence Maximization in Near-Linear Time: A Martingale Approach (2015, methodology): “The reason is that IMM , TIM , and TIM + all provide asymptotic guarantees in terms of the accuracy of their solutions, whereas IRIE is a heuristic method that does not offer any worst-case assurance.”
Information and Influence Propagation in Social Networks (2013, background): “Jung et al. [2012] improve MIA algorithm in both time and space usage by applying belief propagation approach to enable fast global ranking of marginal influence spread, and restricting expensive influence spread computation only for the current seed set. In a very recent paper, Borgs et al. [2012] ”
Influence maximization: near-optimal time complexity meets practical efficiency (2014, methodology): “Due to the space constraint, we omit the comparisons with IRIE and SIMPATH from this presentation, but include them in our online technical report [1].”
Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks (2016, background): “The absolute superiority of SSA and D-SSA are confirmed through extensive experiments on real network data for IM and another topic-aware viral marketing problem, named TVM. Keywords Influence Maximization; Stop-and-Stare; Sampling”