Duality between predictability and reconstructability in complex systems

Abstract

Predicting the evolution of a large system of units using its structure of interaction is a fundamental problem in complex system theory. And so is the problem of reconstructing the structure of interaction from temporal observations. Here, we find an intricate relationship between predictability and reconstructability using an information-theoretical point of view. We use the mutual information between a random graph and a stochastic process evolving on this random graph to quantify their codependence. Then, we show how the uncertainty coefficients, which are intimately related to that mutual information, quantify our ability to reconstruct a graph from an observed time series, and our ability to predict the evolution of a process from the structure of its interactions. Interestingly, we find that predictability and reconstructability, even though closely connected by the mutual information, can behave differently, even in a dual manner. We prove how such duality universally emerges when changing the number of steps in the process, and provide numerical evidence of other dualities occurring near the criticality of multiple different processes evolving on different types of structures.

References in corpus (47)

• Epidemic spreading in scale-free networks
• Measuring Information Transfer
• Epidemic processes in complex networks
• Modeling polypharmacy side effects with graph convolutional networks
• Hyperbolic Geometry of Complex Networks
• Target Space Duality in String Theory
• Simplicial models of social contagion
• Adaptive Coevolutionary Networks: A Review
• Emergence of network features from multiplexity
• Sustaining the Internet with Hyperbolic Mapping
• The Statistical Physics of Real-World Networks
• Entropy measures for complex networks: Toward an information theory of complex topologies
• Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
• Epidemic thresholds of the Susceptible-Infected-Susceptible model on networks: A comparison of numerical and theoretical results
• The entropy of network ensembles
• High-accuracy approximation of binary-state dynamics on networks
• Network Geometry
• Adaptive networks: coevolution of disease and topology
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Reconciling emergences: An information-theoretic approach to identify causal emergence in multivariate data
• Network reconstruction and community detection from dynamics
• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• The entropic origin of disassortativity in complex networks
• Network inference - with confidence - from multivariate time series
• Entropy of stochastic blockmodel ensembles
• Universal nonlinear infection kernel from heterogeneous exposure on higher-order networks
• Gibbs entropy of networks ensembles by cavity methods
• The low-rank hypothesis of complex systems
• Network Geometry Inference using Common Neighbors
• Prudent behaviour accelerates disease transmission
• Model-free quantification of time-series predictability
• Bootstrapping topology and systemic risk of complex network using the fitness model
• Deep learning of contagion dynamics on complex networks
• Propagation dynamics on networks featuring complex topologies
• Eigenvector localization in real networks and its implications for epidemic spreading
• Bayesian inference of network structure from unreliable data
• Interacting contagions are indistinguishable from social reinforcement
• Universal role of correlation entropy in critical phenomena
• Social confinement and mesoscopic localization of epidemics on networks
• Master equation analysis of mesoscopic localization in contagion dynamics on higher-order networks
• netrd: A library for network reconstruction and graph distances
• Threefold way to the dimension reduction of dynamics on networks: an application to synchronization
• Phase transition of the susceptible-infected-susceptible dynamics on time-varying configuration model networks
• The behaviour of information flow near criticality
• Uncertainty Reduction for Stochastic Processes on Complex Networks
• Beyond Wilson-Cowan dynamics: oscillations and chaos without inhibition
• Finite size analysis of the detectability limit of the stochastic block model

Cited by in corpus (2)

• Synergistic signatures of group mechanisms in higher-order systems
• Tensor product algorithms for inference of contact network from epidemiological data