State aggregations in Markov chains and block models of networks
arXiv:2005.00337 · doi:10.1103/PhysRevLett.127.078301
Abstract
We consider state-aggregation schemes for Markov chains from an information-theoretic perspective. Specifically, we consider aggregating the states of a Markov chain such that the mutual information of the aggregated states separated by T time steps is maximized. We show that for T = 1 this approach recovers the maximum-likelihood estimator of the degree-corrected stochastic block model as a particular case, thereby enabling us to explain certain features of the likelihood landscape of this popular generative network model from a dynamical lens. We further highlight how we can uncover coherent, long-range dynamical modules for which considering a time-scale T >> 1 is essential, using synthetic flows and real-world ocean currents, where we are able to recover the fundamental features of the surface currents of the oceans.
arXiv comment18 pages, 13 figures
References in corpus (25)
- Finding and evaluating community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Assortative mixing in networks
- Maps of random walks on complex networks reveal community structure
- Stochastic blockmodels and community structure in networks
- Community detection in networks: A user guide
- Random walks and diffusion on networks
- Complex networks in climate dynamics - Comparing linear and nonlinear network construction methods
- Computational Mechanics: Pattern and Prediction, Structure and Simplicity
- The ground truth about metadata and community detection in networks
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Self-similarity of complex networks and hidden metric spaces
- Parsimonious module inference in large networks
- Hydrodynamic provinces and oceanic connectivity from a transport network help designing marine reserves
- The many facets of community detection in complex networks
- Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
- Graph partitions and cluster synchronization in networks of oscillators
- Modeling sequences and temporal networks with dynamic community structures
- Generalized communities in networks
- Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
- Correlation networks from flows. The case of forced and time-dependent advection-diffusion dynamics
- Multiscale dynamical embeddings of complex networks
- Inferring hidden Markov models from noisy time sequences: a method to alleviate degeneracy in molecular dynamics
- Entrograms and coarse graining of dynamics on complex networks