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 (14)

• Hyperbolic Geometry of Complex Networks
• Adaptive Coevolutionary Networks: A Review
• Emergence of network features from multiplexity
• Sustaining the Internet with Hyperbolic Mapping
• 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
• Adaptive networks: coevolution of disease and topology
• The entropic origin of disassortativity in complex networks
• The low-rank hypothesis of complex systems
• Model-free quantification of time-series predictability
• Propagation dynamics on networks featuring complex topologies
• Universal role of correlation entropy in critical phenomena
• Beyond Wilson-Cowan dynamics: oscillations and chaos without inhibition

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