SODA Conference 2014 Conference Paper
Maximizing Social Influence in Nearly Optimal Time
- Christian Borgs
- Michael Brautbar
- Jennifer T. Chayes
- Brendan Lucier
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, for any ∊ > 0, in time O (( m + n )∊ −3 log n ). Our algorithm is runtime-optimal (up to a logarithmic factor) and substantially improves upon the previously best-known algorithms which run in time Ω( mnk · POLY(∊ −1 )). Furthermore, our algorithm can be modified to allow early termination: if it is terminated after O ( β ( m + n ) log n ) steps for some β < 1 (which can depend on n ), then it returns a solution with approximation factor O ( β ). Finally, we show that this runtime is optimal (up to logarithmic factors) for any β and fixed seed size k.