Efficient influence maximization in social networks

By Yajun Wang, Siyu Yang. 2009

2,328 citations recorded by the source corpus.

Influence maximization is the problem of finding a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. In this paper, we study the efficient influence maximization from two complementary directions. One is to improve the original greedy algorithm of [5] and its improvement [7] to further reduce its running time, and the second is to propose new degree discount heuristics that improves influence spread. We evaluate our algorithms by experiments on two large academic collaboration graphs obtained from the online archival database arXiv.org. Our experimental results show that (a) our improved greedy algorithm achieves better running time comparing with the improvement of [7] with matching influence spread, (b) our degree discount heuristics achieve much better influence spread than classic degree and centrality-based heuristics, and when tuned for a specific influence cascade model, it achieves almost matching influence thread with the greedy algorithm, and more importantly (c) the degree discount heuristics run only in milliseconds while even the improved greedy algorithms run in hours in our experiment graphs with a few tens of thousands of nodes. Based on our results, we believe that fine-tuned heuristics may provide truly scalable solutions to the influence maximization problem with satisfying influence spread and blazingly fast running time. Therefore, contrary to what implied by the conclusion of [5] that traditional heuristics are outperformed by the greedy approximation algorithm, our results shed new lights on the research of heuristic algorithms.

Subfields: Computer Networks and Communications, 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 Statistical and Nonlinear Physics

Citations in the corpus

Scalable Influence Estimation in Continuous-Time Diffusion Networks (2013, methodology): “Compared to [2], the novel application of Cohen’s algorithm arises for estimating influence for multiple sources, which drastically reduces the computation by cleverly using the least-label list from single source.”
Influence maximization: near-optimal time complexity meets practical efficiency (2014, background): “Empirically, it runs in days even when n and m are merely a few thousands [7].”
Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process (2012, background): “Motivated by viral marketing, influence maximization emerges as a fundamental data mining problem concerning the propagation of ideas, opinions, and innovations through social networks.”
CELF++: optimizing the greedy algorithm for influence maximization in social networks (2011, methodology): “The first source is tackled by estimating the spread using Monte Carlo simulation or by using heuristics [4, 6, 2, 5, 1, 3].”
A Data-Based Approach to Social Influence Maximization (2011, methodology): “In spite of this big improvement their method still faces serious scalability issues [3], which has motivated recent works on efficient heuristics for overcoming the efficiency and scalability limits of the greedy algorithm [11, 3, 2, 4].”
Recommender Systems (2016, neutral): “A degreediscount heuristic was proposed in [152].”
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”
Community-based greedy algorithm for mining top-K influential nodes in mobile social networks (2010, methodology): “NewGreedy[4].”
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”
Vital nodes identification in complex networks (2016, methodology): “[207] proposed a so-called degree discount algorithm, which performs almost the same to the greedy algorithm [200] in accuracy while runs more than one-millionth faster than the fastest greedy algorithm.”
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).”
Prosocial learning agents solve generalized Stag Hunts better than selfish ones (2017, background): “We focus on two studied extension of the Stag Hunt: games on networks (Jackson, 2010; Morris, 2000; Chen et al., 2009) and multi-player ‘weak link’ games (Van Huyck et al.”
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).”
A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks (2011, methodology): “[10] present an efficient algorithm to find the topnodes in a social network and this algorithm improves upon the greedy algorithm of Kempe et al.”
A Survey of Signed Network Mining in Social Media (2015, background): “Information Diffusion Information diffusion can enable various online applications such as effective viral marketing and has attracted increasing attention [Kempe et al. 2003; Chen et al. 2009].”
Scalable influence maximization for prevalent viral marketing in large-scale social networks (2010, methodology): “We compare our heuristic with both the greedy algorithm [10, 14, 4 ] and several existing heuristics including the degree discount heuristics of [4], the shortest-path based heuristics of [11], and the popular PageRank algorithm [2] for ranking web pages.”
IRIE: Scalable and Robust Influence Maximization in Social Networks (2011, methodology): “To estimate influence function σ(S) efficiently, Monte-Carlo simulation and other heuristics have been used in various previous works [1], [5], [7], [6], [3], [12], [8], [7], [16].”
Influence Maximization on Social Graphs: A Survey (2018, methodology): “They either adopt a simple discount proxy for influence estimation (DEGDIS [59]) or generalize the PageRank proxy (GROUPPR [65] and IRIE [63]).”