Timezone: »

 
Poster
Computing and maximizing influence in linear threshold and triggering models
Justin Khim · Varun Jog · Po-Ling Loh

Mon Dec 05 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #94
in Monday Posters »

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.

Keywords: Information Theory · (Other) Statistics · Combinatorial Optimization · (Application) Social Networks · Graph-based Learning · (Other) Machine Learning Topics
[ PDF] 

Author Information

Justin Khim (University of Pennsylvania)
Varun Jog (University of Wisconsin-Madison)
Po-Ling Loh (Berkeley)

More from the Same Authors