On the Convexity of Latent Social Network Inference

By Seth A. Myers, Jure Leskovec. 2010

313 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Supervised random walks: predicting and recommending links in social networks (2010, background): “For example, the network inference problem [13, 24] can be cast as a link prediction problem where no knowledge of the network is given.”
Modeling Information Propagation with Survival Theory (2013, background): “In recent years, many network inference algorithms have been developed (Saito et al., 2009; Gomez-Rodriguez et al., 2010; 2011; 2013; Myers & Leskovec, 2010; Snowsill et al., 2011; Netrapalli & Sanghavi, 2012; Gomez-Rodriguez & Sch¨olkopf, 2012; Wang et al., 2012).”
Learning Social Infectivity in Sparse Low-rank Networks Using Multi-dimensional Hawkes Processes (2013, background): “In [12, 15], continuous-time models are proposed to recover sparse influence network but the models can not handle recurrent events and they do not take into account the low-rank network structure.”
Uncovering the Temporal Dynamics of Diffusion Networks (2011, methodology): “Remarkably, introducing continuous temporal dynamics, allowing variable transmission rates across edges, and avoiding further assumptions dramatically simpliﬁed the problem compared with previous approaches (Gomez-Rodriguez et al., 2010; Meyers & Leskovec, 2010).”
Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems (2016, methodology): “he compressive sensing paradigm (as discussed in preceding sections) is not applicable, notwithstanding the methods of alternative sparsity enforcing regularizers and convex optimization used in Ref. [277] to infer networks. The idea in Ref. [37] was then to develop a scheme to implement the highly ”
Inferring Networks of Diffusion and Influence (2012, unknown): “For each edge (i, j), CONNIE infers a prior probability ßi, j and NETRATE infers a transmission rate ai, j.”
Learning Graphs From Data: A Signal Representation Perspective (2018, methodology): “wij Given the set of nodes infected as well as the time of infection in each observed cascade, and assuming that cascades are independent and identically distributed, the likelihood of a graph with adjacency matrix W (with wij being the ijth entry) is derived explicitly in [8], and it is further sho”
Learning Networks of Heterogeneous Influence (2012, unknown): “In contrast to previous state-of-the-art, such as NETRATE, NETINF and CONNIE, KernelCascade makes no restricted assumption on the specific form of the transmission function over network edges.”
Uncover Topic-Sensitive Information Diffusion Networks (2013, background): “A better understanding of the temporal dynamics of diffusion networks can potentially provide us a better prediction of the occurrence time of a future event.”