A dynamical approach to block structure analysis

In this work we analyse diffusion processes unfolding on a complex topology. We build an information theoretical framework with the aim of unveiling mesoscopic structures influencing the evolution of the dynamical system, such as core-periphery, community structure, or other types of (block) patterns. In particular, we take advantage of the mutual information between samples of a dynamics aggregated at the level of blocks drawn at every τ time steps, as a measure of dynamical alteration enforced by the projection to the block structure (see Figure A). We show that using this perspective we can recover the degree corrected stochastic block model (DC–SBM) for the special case in which we examine consecutive time steps (τ =1) on a binary undirected network. On one hand this allows to employ efficient algorithmic strategies developed in the contest of DC–SBM. On the other hand, our results provide a new dynamical interpretation of the block model and suggest natural generalizations, which we explore further in this work.
We highlight how our dynamical approach enables us to detect natural structures that won’t be appropriately classified using standard DC–SBMs. Consider as an illustrative example the network drawn in Figure B. Despite the fact that a natural mesoscopic structure (the two cycles) is present and well aligned with a time-scale separation of the dynamics, fitting an SBM (here done using a minimum description length approach [1]) leads to an overfit of this network. However, over time the diffusion process will mix in both parts of the network individually, leading to long-term dynamical similarity that is effectively block structured again (see Figure). By considering longer time-scales in the evolution of the diffusion process our approach is thus able to pick up this structure naturally. Furthermore, we discuss how our viewpoint is not bound to a simple network paradigm but is effectively applicable to a general set of Markov processes, including higher order Markov processes, or empirical trajectory data, for which no explicit network model has to be available [2,3].