Entrograms and coarse graining of dynamics on complex networks
arXiv:1711.01987 · doi:10.1093/comnet/cnx055
Abstract
Using an information theoretic point of view, we investigate how a dynamics acting on a network can be coarse grained through the use of graph partitions. Specifically, we are interested in how aggregating the state space of a Markov process according to a partition impacts on the thus obtained lower-dimensional dynamics. We highlight that for a dynamics on a particular graph there may be multiple coarse grained descriptions that capture different, incomparable features of the original process. For instance, a coarse graining induced by one partition may be commensurate with a time-scale separation in the dynamics, while another coarse graining may correspond to a different lower-dimensional dynamics that preserves the Markov property of the original process. Taking inspiration from the literature of Computational Mechanics, we find that a convenient tool to summarise and visualise such dynamical properties of a coarse grained model (partition) is the entrogram. The entrogram gathers certain information-theoretic measures, which quantify how information flows across time steps. These information theoretic quantities include the entropy rate, as well as a measure for the memory contained in the process, i.e., how well the dynamics can be approximated by a first order Markov process. We use the entrogram to investigate how specific macro-scale connection patterns in the state-space transition graph of the original dynamics result in desirable properties of coarse grained descriptions. We thereby provide a fresh perspective on the interplay between structure and dynamics in networks, and the process of partitioning from an information theoretic perspective. We focus on networks that may be approximated by both a core-periphery or a clustered organization, and highlight that each of these coarse grained descriptions can capture different aspects of a Markov process acting on the network.
arXiv comment17 pages, 6 figues
References in corpus (32)
- Finding and evaluating community structure in networks
- Epidemic spreading in scale-free networks
- Cooperative Game Theory Approaches for Network Partitioning
- Maps of random walks on complex networks reveal community structure
- Community detection algorithms: a comparative analysis
- Stochastic blockmodels and community structure in networks
- Community detection in networks: A user guide
- Diffusion dynamics on multiplex networks
- An information-theoretic framework for resolving community structure in complex networks
- Random walks and diffusion on networks
- Mixture models and exploratory analysis in networks
- Network Synchronization, Diffusion, and the Paradox of Heterogeneity
- Spectral clustering and the high-dimensional stochastic blockmodel
- The ground truth about metadata and community detection in networks
- Memory in network flows and its effects on spreading dynamics and community detection
- Consistency of spectral clustering in stochastic block models
- Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
- Community Detection as an Inference Problem
- 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
- Spectral coarse-graining of complex networks
- Diffusion on networked systems is a question of time or structure
- Detection of Core-Periphery Structure in Networks Using Spectral Methods and Geodesic Paths
- Generalized communities in networks
- Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
- Damage Spreading and Opinion Dynamics on Scale Free Networks
- Finding and testing network communities by lumped Markov chains
- Opinion dynamics and synchronization in a network of scientific collaborations
- Diffusion geometry unravels the emergence of functional clusters in collective phenomena
- Using higher-order Markov models to reveal flow-based communities in networks
- Spreading dynamics on networks: the role of burstiness, topology and non-stationarity