Timezone: »
We establish upper and lower bounds for the influence of a set of nodes in certain types of contagion models. We derive two sets of bounds, the first designed for linear threshold models, and the second more broadly applicable to a general class of triggering models, which subsumes the popular independent cascade models, as well. We quantify the gap between our upper and lower bounds in the case of the linear threshold model and illustrate the gains of our upper bounds for independent cascade models in relation to existing results. Importantly, our lower bounds are monotonic and submodular, implying that a greedy algorithm for influence maximization is guaranteed to produce a maximizer within a (1 - 1/e)-factor of the truth. Although the problem of exact influence computation is NP-hard in general, our bounds may be evaluated efficiently. This leads to an attractive, highly scalable algorithm for influence maximization with rigorous theoretical guarantees.
Author Information
Justin Khim (University of Pennsylvania)
Varun Jog (University of Wisconsin-Madison)
Po-Ling Loh (Berkeley)
More from the Same Authors
-
2020 Workshop: Deep Learning through Information Geometry »
Pratik Chaudhari · Alexander Alemi · Varun Jog · Dhagash Mehta · Frank Nielsen · Stefano Soatto · Greg Ver Steeg -
2019 : Invited Talk: Varun Jog »
Varun Jog -
2014 Poster: Concavity of reweighted Kikuchi approximation »
Po-Ling Loh · Andre Wibisono -
2013 Poster: Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima »
Po-Ling Loh · Martin J Wainwright -
2013 Spotlight: Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima »
Po-Ling Loh · Martin J Wainwright -
2012 Poster: No voodoo here! Learning discrete graphical models via inverse covariance estimation »
Po-Ling Loh · Martin J Wainwright -
2012 Oral: No voodoo here! Learning discrete graphical models via inverse covariance estimation »
Po-Ling Loh · Martin J Wainwright -
2011 Poster: High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity »
Po-Ling Loh · Martin J Wainwright -
2011 Oral: High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity »
Po-Ling Loh · Martin J Wainwright