Missing and spurious interactions and the reconstruction of complex networks

By Roger Guimerà, Marta Sales-Pardo. Proceedings of the National Academy of Sciences of the United States of America, 2009

720 citations recorded by the source corpus.

Network analysis is currently used in a myriad of contexts, from identifying potential drug targets to predicting the spread of epidemics and designing vaccination strategies and from finding friends to uncovering criminal activity. Despite the promise of the network approach, the reliability of network data is a source of great concern in all fields where complex networks are studied. Here, we present a general mathematical and computational framework to deal with the problem of data reliability in complex networks. In particular, we are able to reliably identify both missing and spurious interactions in noisy network observations. Remarkably, our approach also enables us to obtain, from those noisy observations, network reconstructions that yield estimates of the true network properties that are more accurate than those provided by the observations themselves. Our approach has the potential to guide experiments, to better characterize network data sets, and to drive new discoveries.

Subfields: Experimental and Cognitive Psychology, Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/e2b515d82a3e7c8361538f4757eb712ceb36e50b

How researchers see this paper

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

In Experimental and Cognitive Psychology

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Leaders in Social Networks, the Delicious Case (2011, background): “Tolerance of ranking against spurious and missing links, i.e. false positive and false negative connections, is crucial when network structure is subject to noisy observations [17].”
The statistical physics of real-world networks (2018, background): “For natural and biological networks, collecting all kinds of interactions is highly demanding because of technological limitations or high experimental costs [103, 104].”
Structure and dynamics of molecular networks: A novel paradigm of drug discovery: A comprehensive review (2012, methodology): “…a stochastic bloc model, a probabilistic model, or by using hypergraphs (Albert & Albert, 2004; Liben-Nowell & Kleinberg, 2007; Yan et al., 2007a; Guimera & Sales-Pardo, 2009; Lu et al., 2009; Zhou et al., 2009; Chen et al., 2012a; Eronen & Toivonen, 2012; Hu et al., 2012; Musmeci et al., in…”
Link prediction in social networks: the state-of-the-art (2014, background): “In stochastic block model, nodes in the network are divided into several groups and nodes in the same group have same status [58].”
Learning Latent Block Structure in Weighted Networks (2014, methodology): “In particular, we consider predicting the existence or the weight of some unobserved interaction, a similar task to missing and spurious link prediction [8, 14].”
Hierarchical block structures and high-resolution model selection in large networks (2013, methodology): “We also predict that it should serve as a more reﬁned method of detecting missing information in networks [23, 44], as well as for the prediction of the network evolution [87], determining the more salient topological features [88, 89], or large-scale functional summaries of the network topology…”
From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks (2013, background): “In the Stochastic Block Model or SBM (Guimerà and Sales-Pardo, 2009), a general network model in which a network is partitioned into groups, the probability that two nodes are connected only depends on the groups they belong to.”
Toward link predictability of complex networks (2015, methodology): “The SBM (25) approach is one of the most general network models.”
Link Prediction in Complex Networks: A Survey (2010, methodology): “Given a partition M where each node belongs to one group and the connecting probability for two nodes respectively in groups α and β is denoted by Qαβ (Qαα represents the probability that two nodes within group α are connected), then the likelihood of the observed network structure is [18]”
Community detection in networks: A user guide (2016, methodology): “The standard approach is to fit a generative network model on the data (Ball et al., 2011; Guimerà and Sales-Pardo, 2009; Hastings, 2006; Karrer and Newman, 2011; Newman and Leicht, 2007; Peixoto, 2014).”