Xinran He - University of Southern California

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

similar documents