@inproceedings{borgs2014maximizing,
author = {Borgs, Christian and Brautbar, Michael and Chayes, Jennifer and Lucier, Brendan},
title = {Maximizing Social Influence in Nearly Optimal Time},
booktitle = {Proceedings of the 25nd Annual ACM-SIAM Symposium on Discrete Algorithm (SODA)},
year = {2014},
month = {January},
abstract = {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 Omesdfsdfmnk 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.},
url = {http://approjects.co.za/?big=en-us/research/publication/maximizing-social-influence-nearly-optimal-time/},
pages = {946-957},
edition = {Proceedings of the 25nd Annual ACM-SIAM Symposium on Discrete Algorithm (SODA)},
}