On the Convexity of Latent Social Network Inference

Abstract

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 of thousands of nodes in a matter of minutes.

NIPS, 2010

Cited by in corpus (21)

• Uncovering the Temporal Dynamics of Diffusion Networks
• Reconstructing propagation networks with natural diversity and identifying hidden sources
• Tracking Switched Dynamic Network Topologies from Information Cascades
• Submodular Inference of Diffusion Networks from Multiple Trees
• Deep Collaborative Embedding for information cascade prediction
• Capturing Dynamics of Information Diffusion in SNS: A Survey of Methodology and Techniques
• Learning Dynamic and Personalized Comorbidity Networks from Event Data using Deep Diffusion Processes
• Diffusion-Aware Sampling and Estimation in Information Diffusion Networks
• Link Prediction in Graphs with Autoregressive Features
• Structure and Dynamics of Information Pathways in Online Media
• Learning Network Structures from Contagion
• Limits of Multilayer Diffusion Network Inference in Social Media Research
• Latent Network Embedding via Adversarial Auto-encoders
• Graph Structure Learning from Unlabeled Data for Event Detection
• From #Jobsearch to #Mask: Improving COVID-19 Cascade Prediction with Spillover Effects
• Learning and Optimization with Submodular Functions
• GhostLink: Latent Network Inference for Influence-aware Recommendation
• Temporal similarity metrics for latent network reconstruction: The role of time-lag decay
• On a Bernoulli Autoregression Framework for Link Discovery and Prediction
• Influence Estimation and Maximization via Neural Mean-Field Dynamics
• Joint Network Topology Inference via Structured Fusion Regularization