Maximizing Social Influence in Nearly Optimal Time

By Christian Borgs, Mickey Brautbar, Jennifer Tour Chayes, Brendan Lucier. ACM-SIAM Symposium on Discrete Algorithms, 2012

939 citations recorded by the source corpus.

Diffusion is a fundamental graph process, underpinning such phenomena as epidemic disease contagion and the spread of innovation by word-of-mouth. We address the algorithmic problem of finding a set of k initial seed nodes in a network so that the expected size of the resulting cascade is maximized, under the standard independent cascade model of network diffusion. Runtime is a primary consideration for this problem due to the massive size of the relevant input networks. We provide a fast algorithm for the influence maximization problem, obtaining the near-optimal approximation factor of (1 - 1/e - epsilon), for any epsilon > 0, in time O((m+n)k log(n) / epsilon^2). Our algorithm is runtime-optimal (up to a logarithmic factor) and substantially improves upon the previously best-known algorithms which run in time Omega(mnk POLY(1/epsilon)). Furthermore, our algorithm can be modified to allow early termination: if it is terminated after O(beta(m+n)k log(n)) steps for some beta < 1 (which can depend on n), then it returns a solution with approximation factor O(beta). Finally, we show that this runtime is optimal (up to logarithmic factors) for any beta and fixed seed size k.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/d7f9c3253552e13f24c3b73bc055ef60388af57c

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

Influence Maximization in Near-Linear Time: A Martingale Approach (2015, methodology): “In particular, methods [5,8,20,25,29] that provide (1− 1/e− ε)-approximation solutions often require days to process small social networks with several thousands of nodes and edges; on the other hand, techniques that offer empirical efficiency rely on heuristics, due to which they are unable to offe”
Topological Recurrent Neural Network for Diffusion Prediction (2017, methodology): “Besides, the IC and LT models also enable an important research direction of influence maximization [8], [9], [10].”
Influence maximization: near-optimal time complexity meets practical efficiency (2014, methodology): “[4] avoid the limitation of Greedy and propose a drastically different method for influence maximization under the IC model.”
Influence Maximization on Social Graphs: A Survey (2018, methodology): “Borgs et al. [69] are the ﬁrst to discover that it is not necessary to estimate the inﬂuence using sketches generated by operating on the entire graph.”
Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks (2016, methodology): “Viral Marketing, in which brand-awareness information is widely spread via the word-of-mouth effect, has emerged as one of the most effective marketing channels.”