Browse
Submit Data
Databases
API
Help

Dataset Information

17 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Fundamental limitations of network reconstruction from temporal data.

ABSTRACT: Inferring properties of the interaction matrix that characterizes how nodes in a networked system directly interact with each other is a well-known network reconstruction problem. Despite a decade of extensive studies, network reconstruction remains an outstanding challenge. The fundamental limitations governing which properties of the interaction matrix (e.g. adjacency pattern, sign pattern or degree sequence) can be inferred from given temporal data of individual nodes remain unknown. Here, we rigorously derive the necessary conditions to reconstruct any property of the interaction matrix. Counterintuitively, we find that reconstructing any property of the interaction matrix is generically as difficult as reconstructing the interaction matrix itself, requiring equally informative temporal data. Revealing these fundamental limitations sheds light on the design of better network reconstruction algorithms that offer practical improvements over existing methods.

SUBMITTER: Angulo MT

PROVIDER: S-EPMC5332581 | biostudies-literature | 2017 Feb

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Fundamental limitations of network reconstruction from temporal data.

Angulo Marco Tulio MT Moreno Jaime A JA Lippner Gabor G Barabási Albert-László AL Liu Yang-Yu YY

Journal of the Royal Society, Interface 20170201 127

Inferring properties of the interaction matrix that characterizes how nodes in a networked system directly interact with each other is a well-known network reconstruction problem. Despite a decade of extensive studies, network reconstruction remains an outstanding challenge. The fundamental limitations governing which properties of the interaction matrix (e.g. adjacency pattern, sign pattern or degree sequence) can be inferred from given temporal data of individual nodes remain unknown. Here, we ...[more]

PMID: 28148769

Similar Datasets

Fundamental limitations on efficiently forecasting certain epidemic measures in network models.

Project description:The ongoing COVID-19 pandemic underscores the importance of developing reliable forecasts that would allow decision makers to devise appropriate response strategies. Despite much recent research on the topic, epidemic forecasting remains poorly understood. Researchers have attributed the difficulty of forecasting contagion dynamics to a multitude of factors, including complex behavioral responses, uncertainty in data, the stochastic nature of the underlying process, and the high sensitivity of the disease parameters to changes in the environment. We offer a rigorous explanation of the difficulty of short-term forecasting on networked populations using ideas from computational complexity. Specifically, we show that several forecasting problems (e.g., the probability that at least a given number of people will get infected at a given time and the probability that the number of infections will reach a peak at a given time) are computationally intractable. For instance, efficient solvability of such problems would imply that the number of satisfying assignments of an arbitrary Boolean formula in conjunctive normal form can be computed efficiently, violating a widely believed hypothesis in computational complexity. This intractability result holds even under the ideal situation, where all the disease parameters are known and are assumed to be insensitive to changes in the environment. From a computational complexity viewpoint, our results, which show that contagion dynamics become unpredictable for both macroscopic and individual properties, bring out some fundamental difficulties of predicting disease parameters. On the positive side, we develop efficient algorithms or approximation algorithms for restricted versions of forecasting problems.

| S-EPMC8794801 | biostudies-literature

Fundamental limitations on distillation of quantum channel resources.

Project description:Quantum channels underlie the dynamics of quantum systems, but in many practical settings it is the channels themselves that require processing. We establish universal limitations on the processing of both quantum states and channels, expressed in the form of no-go theorems and quantitative bounds for the manipulation of general quantum channel resources under the most general transformation protocols. Focusing on the class of distillation tasks - which can be understood either as the purification of noisy channels into unitary ones, or the extraction of state-based resources from channels - we develop fundamental restrictions on the error incurred in such transformations, and comprehensive lower bounds for the overhead of any distillation protocol. In the asymptotic setting, our results yield broadly applicable bounds for rates of distillation. We demonstrate our results through applications to fault-tolerant quantum computation, where we obtain state-of-the-art lower bounds for the overhead cost of magic state distillation, as well as to quantum communication, where we recover a number of strong converse bounds for quantum channel capacity.

| S-EPMC8292459 | biostudies-literature

Gene network reconstruction from microarray data.

Project description:BACKGROUND:Often, software available for biological pathways reconstruction rely on literature search to find links between genes. The aim of this study is to reconstruct gene networks from microarray data, using Graphical Gaussian models. RESULTS:The GeneNet R package was applied to the Eadgene chicken infection data set. No significant edges were found for the list of differentially expressed genes between conditions MM8 and MA8. On the other hand, a large number of significant edges were found among 85 differentially expressed genes between conditions MM8 and MM24. CONCLUSION:Many edges were inferred from the microarray data. Most of them could, however, not be validated using other pathway reconstruction software. This was partly due to the fact that a quite large proportion of the differentially expressed genes were not annotated. Further biological validation is therefore needed for these networks, using for example in vitro invalidation of genes.

| S-EPMC2712742 | biostudies-literature

Limitations of the iterative electron density reconstruction algorithm from solution scattering data.

Project description: Not available

| S-EPMC7612988 | biostudies-literature

Reconstruction of the temporal signaling network in Salmonella-infected human cells.

Project description:Salmonella enterica is a bacterial pathogen that usually infects its host through food sources. Translocation of the pathogen proteins into the host cells leads to changes in the signaling mechanism either by activating or inhibiting the host proteins. Given that the bacterial infection modifies the response network of the host, a more coherent view of the underlying biological processes and the signaling networks can be obtained by using a network modeling approach based on the reverse engineering principles. In this work, we have used a published temporal phosphoproteomic dataset of Salmonella-infected human cells and reconstructed the temporal signaling network of the human host by integrating the interactome and the phosphoproteomic dataset. We have combined two well-established network modeling frameworks, the Prize-collecting Steiner Forest (PCSF) approach and the Integer Linear Programming (ILP) based edge inference approach. The resulting network conserves the information on temporality, direction of interactions, while revealing hidden entities in the signaling, such as the SNARE binding, mTOR signaling, immune response, cytoskeleton organization, and apoptosis pathways. Targets of the Salmonella effectors in the host cells such as CDC42, RHOA, 14-3-3?, Syntaxin family, Oxysterol-binding proteins were included in the reconstructed signaling network although they were not present in the initial phosphoproteomic data. We believe that integrated approaches, such as the one presented here, have a high potential for the identification of clinical targets in infectious diseases, especially in the Salmonella infections.

| S-EPMC4507143 | biostudies-literature

Reply to: Limitations of the iterative electron density reconstruction algorithm from solution scattering data.

Project description: Not available

| S-EPMC8284390 | biostudies-literature

Fundamental insights on when social network data are most critical for conservation planning.

Project description:As declines in biodiversity accelerate, there is an urgent imperative to ensure that every dollar spent on conservation counts toward species protection. Systematic conservation planning is a widely used approach to achieve this, but there is growing concern that it must better integrate the human social dimensions of conservation to be effective. Yet, fundamental insights about when social data are most critical to inform conservation planning decisions are lacking. To address this problem, we derived novel principles to guide strategic investment in social network information for systematic conservation planning. We considered the common conservation problem of identifying which social actors, in a social network, to engage with to incentivize conservation behavior that maximizes the number of species protected. We used simulations of social networks and species distributed across network nodes to identify the optimal state-dependent strategies and the value of social network information. We did this for a range of motif network structures and species distributions and applied the approach to a small-scale fishery in Kenya. The value of social network information depended strongly on both the distribution of species and social network structure. When species distributions were highly nested (i.e., when species-poor sites are subsets of species-rich sites), the value of social network information was almost always low. This suggests that information on how species are distributed across a network is critical for determining whether to invest in collecting social network data. In contrast, the value of social network information was greatest when social networks were highly centralized. Results for the small-scale fishery were consistent with the simulations. Our results suggest that strategic collection of social network data should be prioritized when species distributions are un-nested and when social networks are likely to be centralized.

| S-EPMC7754422 | biostudies-literature

Epidemiologically optimal static networks from temporal network data.

Project description:One of network epidemiology's central assumptions is that the contact structure over which infectious diseases propagate can be represented as a static network. However, contacts are highly dynamic, changing at many time scales. In this paper, we investigate conceptually simple methods to construct static graphs for network epidemiology from temporal contact data. We evaluate these methods on empirical and synthetic model data. For almost all our cases, the network representation that captures most relevant information is a so-called exponential-threshold network. In these, each contact contributes with a weight decreasing exponentially with time, and there is an edge between a pair of vertices if the weight between them exceeds a threshold. Networks of aggregated contacts over an optimally chosen time window perform almost as good as the exponential-threshold networks. On the other hand, networks of accumulated contacts over the entire sampling time, and networks of concurrent partnerships, perform worse. We discuss these observations in the context of the temporal and topological structure of the data sets.

| S-EPMC3715509 | biostudies-literature

Learning a variational network for reconstruction of accelerated MRI data.

Project description:PURPOSE:To allow fast and high-quality reconstruction of clinical accelerated multi-coil MR data by learning a variational network that combines the mathematical structure of variational models with deep learning. THEORY AND METHODS:Generalized compressed sensing reconstruction formulated as a variational model is embedded in an unrolled gradient descent scheme. All parameters of this formulation, including the prior model defined by filter kernels and activation functions as well as the data term weights, are learned during an offline training procedure. The learned model can then be applied online to previously unseen data. RESULTS:The variational network approach is evaluated on a clinical knee imaging protocol for different acceleration factors and sampling patterns using retrospectively and prospectively undersampled data. The variational network reconstructions outperform standard reconstruction algorithms, verified by quantitative error measures and a clinical reader study for regular sampling and acceleration factor 4. CONCLUSION:Variational network reconstructions preserve the natural appearance of MR images as well as pathologies that were not included in the training data set. Due to its high computational performance, that is, reconstruction time of 193 ms on a single graphics card, and the omission of parameter tuning once the network is trained, this new approach to image reconstruction can easily be integrated into clinical workflow. Magn Reson Med 79:3055-3071, 2018. © 2017 International Society for Magnetic Resonance in Medicine.

| S-EPMC5902683 | biostudies-literature

Microbial Community Metabolic Modeling: A Community Data-Driven Network Reconstruction.

Project description:Metabolic network modeling of microbial communities provides an in-depth understanding of community-wide metabolic and regulatory processes. Compared to single organism analyses, community metabolic network modeling is more complex because it needs to account for interspecies interactions. To date, most approaches focus on reconstruction of high-quality individual networks so that, when combined, they can predict community behaviors as a result of interspecies interactions. However, this conventional method becomes ineffective for communities whose members are not well characterized and cannot be experimentally interrogated in isolation. Here, we tested a new approach that uses community-level data as a critical input for the network reconstruction process. This method focuses on directly predicting interspecies metabolic interactions in a community, when axenic information is insufficient. We validated our method through the case study of a bacterial photoautotroph-heterotroph consortium that was used to provide data needed for a community-level metabolic network reconstruction. Resulting simulations provided experimentally validated predictions of how a photoautotrophic cyanobacterium supports the growth of an obligate heterotrophic species by providing organic carbon and nitrogen sources. J. Cell. Physiol. 231: 2339-2345, 2016. © 2016 Wiley Periodicals, Inc.

| S-EPMC5132105 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data