Timezone: »

 
Poster
Learning Influence Functions from Incomplete Observations
Xinran He · Ke Xu · David Kempe · Yan Liu

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #133
in Wednesday Posters »

We study the problem of learning influence functions under incomplete observations of node activations. Incomplete observations are a major concern as most (online and real-world) social networks are not fully observable. We establish both proper and improper PAC learnability of influence functions under randomly missing observations. Proper PAC learnability under the Discrete-Time Linear Threshold (DLT) and Discrete-Time Independent Cascade (DIC) models is established by reducing incomplete observations to complete observations in a modified graph. Our improper PAC learnability result applies for the DLT and DIC models as well as the Continuous-Time Independent Cascade (CIC) model. It is based on a parametrization in terms of reachability features, and also gives rise to an efficient and practical heuristic. Experiments on synthetic and real-world datasets demonstrate the ability of our method to compensate even for a fairly large fraction of missing observations.

Keywords: (Application) Social Networks
[ PDF] 

Author Information

Xinran He (USC)
Ke Xu (USC)
David Kempe (USC)
Yan Liu (University of Southern California)

More from the Same Authors