Source-linked AI summary
Missing and spurious interactions and the reconstruction of complex networks
R. Guimera, M. Sales-Pardo
TL;DR
The paper addresses unreliable network observations by developing a general mathematical and computational framework for identifying missing and spurious interactions. It also reconstructs networks from noisy observations, estimating true network properties more accurately than the observations themselves and helping prioritize experimental investigation.
Problem
Network data can contain missing and spurious interactions, making it difficult to characterize the underlying true network reliably.
Method
The approach models the observed network probabilistically, evaluates link reliability, and uses generative network models to identify suspect interactions and reconstruct the network.
Results
The approach consistently outperforms hierarchical random graph and local algorithms across nearly all tested networks for detecting both missing and spurious interactions, and can estimate true network properties better than direct observation.
Takeaways & Limitations
The method can improve characterization of inaccurate network datasets, identify interactions for experimental probing, and potentially highlight functionally or evolutionarily important interactions.
Takeaways & Limitations
The protein-interaction analysis uses a testing procedure chosen to evaluate reliability separation, not as the most appropriate procedure for analyzing protein-network structure.
Abstract
from arXiv · showhide
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.
General reliability formalism
The framework estimates the reliability of arbitrary network properties by averaging over generative models consistent with an observed network, using Bayesian model weighting.
- General reliability formalism: The observed network is treated as a realization of an underlying probabilistic generative model.The framework allows uncertainty to arise from stochastic network generation, measurement uncertainty, or both.
- General reliability formalism: The probability of a network property is obtained by averaging p(X = x|M) over models M weighted by p(M|AO).Here, p(X = x|M) is the probability that model M generates property value x.
- General reliability formalism: Bayes’ theorem rewrites the model weighting using the likelihood p(AO|M) and prior p(M).The denominator sums the likelihood-weighted priors over candidate models.
- General reliability formalism: The resulting p(X = x|AO) is called the reliability of the X = x measurement.This reliability incorporates the observed network and the model uncertainty.
Stochastic block models
The authors use stochastic block models because they can represent diverse network correlations while remaining empirically grounded and analytically tractable.
- Stochastic block models: Good reliability estimates require model families that are general, empirically grounded, and analytically or computationally tractable.The paper focuses on the family MBM of stochastic block models.
- Stochastic block models: In a stochastic block model, nodes are partitioned into groups, and connection probabilities depend only on the groups of the endpoints.This structure permits calculations of both individual-link and whole-network reliability.
- Stochastic block models: Block models capture modular organization, including relatively denser connections within modules than between them.Real networks often contain overlapping or hierarchically nested modules.
- Stochastic block models: Block models can also capture connectivity correlations based on attributes such as age groups in social networks.Different partitions can represent modules, roles, or demographic groups.
- Stochastic block models: Sampling across the MBM family captures multiple network mechanisms to the degree that they are relevant.The paper describes networks as combinations of modularity, role structure, and other factors.
Link reliability: missing and spurious interactions
The method assigns link reliabilities under stochastic block models and uses them to rank potentially missing or spurious interactions. It is evaluated on curated networks with artificially altered observations and generally outperforms comparison methods.
- Link reliability: missing and spurious interactions: Link reliability is pBM(Aij = 1|AO), the probability that a link truly exists given the whole observed network.The probability is computed under the chosen stochastic block model family without prior model-suitability knowledge.
- Link reliability: missing and spurious interactions: The reliability calculation averages over network partitions, weighting each partition by exp[−H(P)].Relevant partitions are sampled with the Metropolis algorithm because exhaustive summation is impractical.
- Link reliability: missing and spurious interactions: The approach is tested on five manually curated networks treated as true networks, with observations generated by randomly adding or removing links.The benchmark includes karate, dolphin, air transportation, C. elegans neural, and E. coli metabolic networks.
- Link reliability: missing and spurious interactions: Missing interactions are identified by ranking link reliabilities for removed links against true negatives.Spurious interactions are evaluated by adding random links and ranking false positives against true links.
- Link reliability: missing and spurious interactions: Except for one network, the approach consistently outperforms HRG and common-neighbor methods for identifying missing and spurious interactions.It is also consistently accurate across several model-network structures; HRG is slightly better for missing links only when the network is strictly HRG.
Network reliability and network reconstruction
The framework estimates network reliability under stochastic block models, identifies missing and spurious interactions, and reconstructs networks whose properties can better approximate the true network than noisy observations.
- Network reconstruction begins by estimating the probability that a candidate network is the true network given the observed network.
- Reconstructed global network properties were generally closer to those of the true network than properties measured from observations, except for some properties below 10% errors.
- The reconstruction is the maximum a posteriori network, obtained by heuristically maximizing network reliability from the observed network.
- 13% fewer missing and spurious interactions were present in the reconstructed Eastern European air transportation network than in its 20%-error observation.
Application to a protein interaction network
The framework was applied to a yeast protein interaction network to distinguish experimentally reproducible interactions from nonreproducible ones using link reliability alone.
- The yeast network came from affinity purification and mass spectrometry experiments and was restricted to 991 proteins serving as both viable baits and viable prey.
- The evaluation compared interactions observed once with interactions observed twice among proteins used exactly once as bait.
- Only 5 of the 100 interactions with the lowest link reliability were experimentally reproducible.
- 65 of the 100 interactions with the highest link reliability were experimentally reproducible, with chance probability p≥= 2×10^-20.
- The algorithm separated likely spurious from likely correct interactions without using biophysical or biochemical information.
Discussion
The framework supports network reconstruction and experimental prioritization while using stochastic block models to estimate link and network reliabilities. Its sampling and heuristic procedures make these estimates computationally tractable, but the demonstrated protein-network analysis was chosen for testing rather than endorsed as the most appropriate structural analysis.
- Discussion: The method identifies suspect interactions for further experimental probing and improves characterization of inaccurate network data sets.
- Discussion: Very low predicted reliability for a true interaction indicates that its function may be specific and functionally or evolutionarily important.
- Discussion: The protein-interaction analysis was used to test separation of reliable and unreliable interactions, not presented as the most appropriate procedure for analyzing protein-network structure.
- Reliability calculations: Stochastic block models represent networks by node partitions and group-level connection probabilities, allowing link and network reliabilities to be calculated.
- Reliability calculations: The reliability estimates average over possible partitions, with Metropolis sampling used because exhaustive summation is impractical.
- Heuristic network reconstruction: The heuristic reconstruction swaps low-reliability observed links with high-reliability observed non-links when the network reliability increases, stopping after repeated rejected swaps.