Missing and spurious interactions and the reconstruction of complex networks

2009/12/14 by Roger Guimerà, R. Guimera, Marta Sales‐Pardo +1 · 12 citations
Biochemistry, Genetics and Molecular Biology · Physics and Astronomy · Psychology · #Artificial intelligence #Bioinformatics and Genomic Networks #Biological network #Biology #Complex Network Analysis Techniques #Complex network #Computational biology #Computer science #Data mining #Data science #Machine learning #Mental Health Research Topics #Missing data #Network analysis #Network science #Reliability (semiconductor) #Spurious relationship #physics.data-an #q-bio.MN

paper · pdf · doi:10.1073/pnas.0908366106

published as Proc. Natl. Acad. Sci. U. S. A. 106, 22073-22078 (2009)

openalex publication_date 2009/12/14 · arxiv created 2010/04/27 · arxiv updated 2010/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

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.

Citations

• Community structure in social and biological networks
• Characterization of complex networks: A survey of measurements
• The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations
• An expanded genome-scale model of Escherichia coli K-12 (iJR904 GSM/GPR)
• The structure of the nervous system of the nematode Caenorhabditis elegans

Cited by

• Playing the role of weak clique property in link prediction: A friend recommendation model
• Stochastic blockmodels and community structure in networks
• Reconstructing Networks
• Efficient method for estimating the number of communities in a network
• Optimality of variational inference for stochastic block model with\n missing links
• Tensorial and bipartite block models for link prediction in layered networks and temporal networks
• Link prediction with hyperbolic geometry
• Bayesian inference of network structure from unreliable data
• Finding missing edges and communities in incomplete networks
• Disentangling Homophily, Community Structure, and Triadic Closure in Networks
• Estimating the Number of Communities in a Network
• Estimating network structure from unreliable measurements

Related

• On the reconstruction limits of complex networks
• Fundamental limitations of network reconstruction
• Prediction and inference in complex networks: a brief review and perspectives
• Missing data in multiplex networks: a preliminary study
• A surrogate for networks -- How scale-free is my scale-free network?