Missing and Spurious Interactions and the Reconstruction of Complex Networks

Overview

Journal Proc Natl Acad Sci U S A

Specialty Science

Date 2009 Dec 19

PMID 20018705

Citations 131

Authors

Roger Guimera

Marta Sales-Pardo

Affiliations

Soon will be listed here.

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.

Citing Articles

A Generalized Bayesian Stochastic Block Model for Microbiome Community Detection.

Lutz K, Neugent M, Bedi T, De Nisco N, Li Q Stat Med. 2025; 44(3-4):e10291.

PMID: 39853798 PMC: 11760646. DOI: 10.1002/sim.10291.

Link prediction of heterogeneous complex networks based on an improved embedding learning algorithm.

Chai L, Huang R PLoS One. 2025; 20(1):e0315507.

PMID: 39775286 PMC: 11706414. DOI: 10.1371/journal.pone.0315507.

Inconsistency among evaluation metrics in link prediction.

Bi Y, Jiao X, Lee Y, Zhou T PNAS Nexus. 2024; 3(11):pgae498.

PMID: 39564572 PMC: 11574622. DOI: 10.1093/pnasnexus/pgae498.

A One Health framework for exploring zoonotic interactions demonstrated through a case study.

Desvars-Larrive A, Vogl A, Puspitarani G, Yang L, Joachim A, Kasbohrer A Nat Commun. 2024; 15(1):5650.

PMID: 39009576 PMC: 11250852. DOI: 10.1038/s41467-024-49967-7.

The effectiveness of intervention measures on MERS-CoV transmission by using the contact networks reconstructed from link prediction data.

Kim E, Kim Y, Jin H, Lee Y, Lee H, Lee S Front Public Health. 2024; 12:1386495.

PMID: 38827618 PMC: 11140122. DOI: 10.3389/fpubh.2024.1386495.

References

Guimera R, Sales-Pardo M, Nunes Amaral L . Modularity from fluctuations in random graphs and complex networks. Phys Rev E Stat Nonlin Soft Matter Phys. 2004; 70(2 Pt 2):025101. PMC: 2441765. DOI: 10.1103/PhysRevE.70.025101. View

Clauset A, Moore C, Newman M . Hierarchical structure and the prediction of missing links in networks. Nature. 2008; 453(7191):98-101. DOI: 10.1038/nature06830. View

Yu H, Braun P, Yildirim M, Lemmens I, Venkatesan K, Sahalie J . High-quality binary protein interaction map of the yeast interactome network. Science. 2008; 322(5898):104-10. PMC: 2746753. DOI: 10.1126/science.1158684. View

Gavin A, Aloy P, Grandi P, Krause R, Boesche M, Marzioch M . Proteome survey reveals modularity of the yeast cell machinery. Nature. 2006; 440(7084):631-6. DOI: 10.1038/nature04532. View

White J, Southgate E, Thomson J, Brenner S . The structure of the nervous system of the nematode Caenorhabditis elegans. Philos Trans R Soc Lond B Biol Sci. 2012; 314(1165):1-340. DOI: 10.1098/rstb.1986.0056. View

Guimera R, Diaz-Guilera A, Cabrales A, Arenas A . Optimal network topologies for local search with congestion. Phys Rev Lett. 2002; 89(24):248701. DOI: 10.1103/PhysRevLett.89.248701. View

Jansen R, Yu H, Greenbaum D, Kluger Y, Krogan N, Chung S . A Bayesian networks approach for predicting protein-protein interactions from genomic data. Science. 2003; 302(5644):449-53. DOI: 10.1126/science.1087361. View

von Mering C, Krause R, Snel B, Cornell M, Oliver S, Fields S . Comparative assessment of large-scale data sets of protein-protein interactions. Nature. 2002; 417(6887):399-403. DOI: 10.1038/nature750. View

Schafer J, Graham J . Missing data: our view of the state of the art. Psychol Methods. 2002; 7(2):147-77. View

10.

Sales-Pardo M, Guimera R, Moreira A, Nunes Amaral L . Extracting the hierarchical organization of complex systems. Proc Natl Acad Sci U S A. 2007; 104(39):15224-9. PMC: 2000510. DOI: 10.1073/pnas.0703740104. View

11.

Boguna M, Pastor-Satorras R . Epidemic spreading in correlated complex networks. Phys Rev E Stat Nonlin Soft Matter Phys. 2002; 66(4 Pt 2):047104. DOI: 10.1103/PhysRevE.66.047104. View

12.

Newman M . Mixing patterns in networks. Phys Rev E Stat Nonlin Soft Matter Phys. 2003; 67(2 Pt 2):026126. DOI: 10.1103/PhysRevE.67.026126. View

13.

Girvan M, Newman M . Community structure in social and biological networks. Proc Natl Acad Sci U S A. 2002; 99(12):7821-6. PMC: 122977. DOI: 10.1073/pnas.122653799. View

14.

Reed J, Vo T, Schilling C, Palsson B . An expanded genome-scale model of Escherichia coli K-12 (iJR904 GSM/GPR). Genome Biol. 2003; 4(9):R54. PMC: 193654. DOI: 10.1186/gb-2003-4-9-r54. View

15.

Guimera R, Sales-Pardo M, Amaral L . A network-based method for target selection in metabolic networks. Bioinformatics. 2007; 23(13):1616-22. PMC: 2149892. DOI: 10.1093/bioinformatics/btm150. View

16.

Guimera R, Mossa S, Turtschi A, Amaral L . The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles. Proc Natl Acad Sci U S A. 2005; 102(22):7794-9. PMC: 1142352. DOI: 10.1073/pnas.0407994102. View

17.

Nunes Amaral L . A truer measure of our ignorance. Proc Natl Acad Sci U S A. 2008; 105(19):6795-6. PMC: 2383987. DOI: 10.1073/pnas.0802459105. View

18.

Chiang T, Scholtens D . A general pipeline for quality and statistical assessment of protein interaction data using R and Bioconductor. Nat Protoc. 2009; 4(4):535-46. DOI: 10.1038/nprot.2009.26. View

19.

Guimera R, Sales-Pardo M, Amaral L . Classes of complex networks defined by role-to-role connectivity profiles. Nat Phys. 2008; 3(1):63-69. PMC: 2447920. DOI: 10.1038/nphys489. View

20.

Stumpf M, Thorne T, de Silva E, Stewart R, An H, Lappe M . Estimating the size of the human interactome. Proc Natl Acad Sci U S A. 2008; 105(19):6959-64. PMC: 2383957. DOI: 10.1073/pnas.0708078105. View