State aggregations in Markov chains and block models of networks

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.

18 pages, 13 figures

References in corpus (9)

• Maps of random walks on complex networks reveal community structure
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Complex networks in climate dynamics - Comparing linear and nonlinear network construction methods
• 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
• Entrograms and coarse graining of dynamics on complex networks

Cited by in corpus (4)

• Synwalk -- Community Detection via Random Walk Modelling
• Relative, local and global dimension in complex networks
• Measuring dynamical systems on directed hyper-graphs
• Coarse-graining nonequilibrium diffusions with Markov chains