Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem

Abstract

Elements composing complex systems usually interact in several different ways and as such the interaction architecture is well modelled by a multiplex network. However often this architecture is hidden, as one usually only has experimental access to an aggregated projection. A fundamental challenge is thus to determine whether the hidden underlying architecture of complex systems is better modelled as a single interaction layer or results from the aggregation and interplay of multiple layers. Here we show that using local information provided by a random walker navigating the aggregated network one can decide in a robust way if the underlying structure is a multiplex or not and, in the former case, to determine the most probable number of hidden layers. As a byproduct, we show that the mathematical formalism also provides a principled solution for the optimal decomposition and projection of complex, non-Markovian dynamics into a Markov switching combination of diffusive modes. We validate the proposed methodology with numerical simulations of both (i) random walks navigating hidden multiplex networks (thereby reconstructing the true hidden architecture) and (ii) Markovian and non-Markovian continuous stochastic processes (thereby reconstructing an effective multiplex decomposition where each layer accounts for a different diffusive mode). We also state and prove two existence theorems guaranteeing that an exact reconstruction of the dynamics in terms of these hidden jump-Markov models is always possible for arbitrary finite-order Markovian and fully non-Markovian processes. Finally, we showcase the applicability of the method to experimental recordings from (i) the mobility dynamics of human players in an online multiplayer game and (ii) the dynamics of RNA polymerases at the single-molecule level.

arXiv comment40 pages, 24 figures

References in corpus (49)

• Understanding individual human mobility patterns
• Maps of random walks on complex networks reveal community structure
• Catastrophic cascade of failures in interdependent networks
• Statistical physics of social dynamics
• Epidemic processes in complex networks
• Synchronization in complex networks
• Multilayer Networks
• The structure and dynamics of multilayer networks
• Active Particles in Complex and Crowded Environments
• Spatial Networks
• Hierarchical structure and the prediction of missing links in networks
• Dynamical interplay between awareness and epidemic spreading in multiplex networks
• Diffusion dynamics on multiplex networks
• Multirelational Organization of Large-scale Social Networks in an Online World
• Missing and spurious interactions and the reconstruction of complex networks
• The physics of spreading processes in multilayer networks
• Layer aggregation and reducibility of multilayer interconnected networks
• Emergence of network features from multiplexity
• Random Walks on Multiplex Networks
• Abrupt transition in the structural formation of interconnected networks
• Epidemic spreading on interconnected networks
• Percolation Theory on Interdependent Networks Based on Epidemic Spreading
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Estimating dissipation from single stationary trajectories
• Rewarding evolutionary fitness with links between populations promotes cooperation
• Adaptive Importance Sampling in General Mixture Classes
• Multiple percolation transitions in a configuration model of network of networks
• Epidemics in partially overlapped multiplex networks
• Synchronization in networks with multiple interaction layers
• Congestion induced by the structure of multiplex networks
• The new challenges of multiplex networks: measures and models
• Entropy production and Kullback-Leibler divergence between stationary trajectories of discrete systems
• Modeling sequences and temporal networks with dynamic community structures
• Estimating the number of communities in a network
• Understanding mobility in a social petri dish
• Directed transport of active particles over asymmetric energy barriers
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• Irreducibility of multilayer network dynamics: the case of the voter model
• Absorbing and Shattered Fragmentation Transitions in Multilayer Coevolution
• Brownian motion and gambling: from ratchets to paradoxical games
• Efficient exploration of multiplex networks
• Can we neglect the multi-layer structure of functional networks?
• Bayesian Structural Inference for Hidden Processes
• A population Monte Carlo scheme with transformed weights and its application to stochastic kinetic models
• Using higher-order Markov models to reveal flow-based communities in networks
• Strategical incoherence regulates cooperation in social dilemmas on multiplex networks
• Driving interconnected networks to supercriticality
• A nonlinear population Monte Carlo scheme for the Bayesian estimation of parameters of $\alpha$-stable distributions

Cited by in corpus (13)

• Cascading Failures in Complex Networks
• An Evolutionary Game With the Game Transitions Based on the Markov Process
• Multilayer Network Science: from Cells to Societies
• Abrupt transition due to non-local cascade propagation in multiplex systems
• Connecting Network Science and Information Theory
• Algorithmic complexity of multiplex networks
• Detecting Hidden Layers from Spreading Dynamics on Complex Networks
• Multiplex reconstruction with partial information
• Discovering hidden layers in quantum graphs
• Memory Order Decomposition of Symbolic Sequences
• Correlations of network trajectories
• The Limits of Inference in Complex Systems: When Stochastic Models Become Indistinguishable
• Discrimination universally determines reconstruction of multiplex networks