Scalable influence maximization for prevalent viral marketing in large-scale social networks

By Chi Wang, Yajun Wang. 2010

1,817 citations recorded by the source corpus.

Influence maximization, defined by Kempe, Kleinberg, and Tardos (2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. The scalability of influence maximization is a key factor for enabling prevalent viral marketing in large-scale online social networks. Prior solutions, such as the greedy algorithm of Kempe et al. (2003) and its improvements are slow and not scalable, while other heuristic algorithms do not provide consistently good performance on influence spreads. In this paper, we design a new heuristic algorithm that is easily scalable to millions of nodes and edges in our experiments. Our algorithm has a simple tunable parameter for users to control the balance between the running time and the influence spread of the algorithm. Our results from extensive simulations on several real-world and synthetic networks demonstrate that our algorithm is currently the best scalable solution to the influence maximization problem: (a) our algorithm scales beyond million-sized graphs where the greedy algorithm becomes infeasible, and (b) in all size ranges, our algorithm performs consistently well in influence spread --- it is always among the best algorithms, and in most cases it significantly outperforms all other scalable heuristics to as much as 100%--260% increase in influence spread.

Subfields: Computer Networks and Communications, Information Systems, Statistical and Nonlinear Physics

How researchers see this paper

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

In Computer Networks and Communications

In Information Systems

In Statistical and Nonlinear Physics

Citations in the corpus

Scalable Influence Estimation in Continuous-Time Diffusion Networks (2013, methodology): “For INFLUMAX, since it only supports exponential pairwise transmission functions, we fit an exponential distribution per edge.”
IRIE: Scalable and Robust Influence Maximization in Social Networks (2011, methodology): “Among them PMIA [4] algorithm has stood out as the most efficient heuristic so far, which runs three orders of magnitude faster than the optimized greedy algorithm of [5], [7], while maintaining good influence spread in par with the greedy algorithm.”
SIMPATH: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model (2011, methodology): “However, computing exact marginal gain (or exact expected spread) under both the IC and LT models is #P-hard [6], [7].”
Maximizing Social Influence in Nearly Optimal Time (2012, background): “These have focused largely on heuristics, such as assuming that all nodes have relatively low influence or that the input graph is clustered [12, 14, 25, 38], as well as empirically-motivated implementation improvements [27, 13].”
Influence Maximization in Continuous Time Diffusion Networks (2012, methodology): “Efficient influence maximization that uses heuristics to speed up the optimization problem has been proposed (Chen et al., 2009; 2010) and influence maximization has been studied on the context of competing cascades (Bharathi et al., 2007) or under additional constraints (Goyal et al., 2010).”
Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process (2012, methodology): “S”
Influence Maximization in Continuous Time Diffusion Networks (2012, methodology): “Efficient influence maximization that uses heuristics to speed up the optimization problem has been proposed (Chen et al., 2009; 2010) and influence maximization has been studied on the context of competing cascades (Bharathi et al., 2007) or under additional constraints (Goyal et al., 2010).”
Influence Maximization in Near-Linear Time: A Martingale Approach (2015, methodology): “This setting is adopted in previous work [7, 19, 24, 36].”
Influence Maximization on Social Graphs: A Survey (2018, methodology): “The MIA/PMIA [46] model is the most well-known reducedmodel for IC.”
Scalable Influence Maximization in Social Networks under the Linear Threshold Model (2010, methodology): “The new heuristic algorithms proposed in [3], [6], [7] are orders of magnitude faster than”
Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate (2011, methodology): “…with a standard greedy approximation algorithm while being orders of magnitude faster. keywords: influence maximization; social networks; negative opinions; independent cascade model; ∗Author affiliations and emails: W. Chen (contact author), Microsoft Research Asia, China, weic@microsoft.com.”
A Data-Based Approach to Social Influence Maximization (2011, methodology): “[4] W. Chen et al. Scalable influence maximization in social networks under the linear threshold model.”
Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks (2016, background): “Each edge (u, v) ∈ E is associated with a weight w(u, v) ∈ [0, 1] which indicates the probability that u influences v.”