Poster
On the Convexity of Latent Social Network Inference
Seth A Myers · Jure Leskovec

Wed Dec 8th 12:00 -- 12:00 AM @ None #None
in Poster Session »

In many real-world scenarios, it is nearly impossible to collect explicit social network data. In such cases, whole networks must be inferred from underlying observations. Here, we formulate the problem of inferring latent social networks based on network diffusion or disease propagation data. We consider contagions propagating over the edges of an unobserved social network, where we only observe the times when nodes became infected, but not who infected them. Given such node infection times, we then identify the optimal network that best explains the observed data. We present a maximum likelihood approach based on convex programming with a l1-like penalty term that encourages sparsity. Experiments on real and synthetic data reveal that our method near-perfectly recovers the underlying network structure as well as the parameters of the contagion propagation model. Moreover, our approach scales well as it can infer optimal networks on thousands of nodes in a matter of minutes.

Author Information

Seth A Myers (Stanford University)
Jure Leskovec (Stanford University and Pinterest)

More from the Same Authors