Report

Stability of Influence Maximization Xinran He and David Kempe University of Southern California {xinranhe, [email protected] 08/26/2014 Diffusion In Social Networks 0.8 0.2 0.5 0.2 0.6 0.3 0.7 • The adoption of new products can propagate in the social network Diffusion in the social network He & Kempe (USC) Influence Stability KDD 2014 IC Model & Influence Maximization • Independent Cascade (IC) Model: • Each newly activated node has a single chance to activate each inactive neighbor with probability , . • Influence Maximization: • Find people that generate the largest influence spread (i.e. expected number of activated nodes) [KKT 2003] Where do parameters , come from? He & Kempe (USC) Influence Stability KDD 2014 Uncertainty in Influence Strength Diffusion History Network Inference 0.8 Questionnaire 0.5 0.1 0.8 0.6 0.4 Does such instability really exist? Influence Maximization 0.3 0.5 0.6 0.3 0.9 0.6 0.1 0.4 Ground truth network He & Kempe(USC) Influence Stability KDD 2014 An Extreme Example Select one seed = 0.0625 0.055 = 0.0625 0.07 He & Kempe (USC) Influence Stability KDD 2014 An Extreme Example (Cont.) = 0.3 0.35 = 0.3 0.25 He & Kempe (USC) Influence Stability KDD 2014 Diagnosing Instability Given an instance of Influence Maximization, can we diagnose How about thisefficiently network?whether it is stable or unstable? Complete answer 0.5 0.1 ⇒ Computing percolation0.8 threshold of any graph. Partial solution 0.6 0.3 0.8 0.4 Unstable instances ⇒ Fire an alarm correctly. Stable instances He & Kempe (USC) ⇒ Possible false alarms. Influence Stability KDD 2014 Definition of Stability • Model of misestimation: , ′ , , 0 , 1 Definition (Stability of Influence Maximization): An instance (, , , ) is stable if the difference in influence is ′ small for all legal , ∈ , and all seed sets of size . He & Kempe (USC) Influence Stability KDD 2014 Influence Difference Maximization Optimization Problem: max ′max | − ′()| = , ∈, Definition (Influence Difference Maximization) : ′ for all , , Given two instances with probabilities , ≥ , let and ′ be the respective influence functions. Find a set S of size maximizing − ′(). He & Kempe (USC) Influence Stability KDD 2014 Main Theory Result Main Theorem: Under the IC model, − ′() is a non-negative and submodular function of the set (but not monotone). • Random Greedy Algorithm [Buchbinder et al.] • Approximation guarantee: 0.266→ 1/ ( ≪ ||) • Running time: ( 2 ) (:number of Monte-Carlo Simulations) Corollary : Assuming is the seed set returned by maximizing obs with greedy algorithm, we have true ≥ ⋅ true ∗ , where is a constant depending on the given instance. He & Kempe (USC) Influence Stability KDD 2014 Conclusion • Noise is everywhere in social network data Influence Maximization could be unstable Calls into question practicality of algorithmic approaches • Instability can be diagnosed by solving Influence Difference Maximization • Via non-monotone submodular maximization • Experiments on synthetic networks (2D-grid, random regular, SW, PA) and real networks (retweet, collaboration) • 10% relative noise ⇒ Decent approximation • 20% relative noise ⇒ Significant Challenge • Further extension: • Linear Threshold Model, Triggering Model He & Kempe (USC) Influence Stability KDD 2014 Future work • Generalization to other diffusion models. • Generalized Threshold (GT) model • Generalization to other misestimation models. • Current assumption: each deviation is bounded • What if the total (squared) deviation is bounded? • Big picture: How accurate are our diffusion models? He & Kempe (USC) Influence Stability KDD 2014