title: Encoding dynamics for multiscale community detection: Markov time sweeping for the map equation.
abstract: The detection of community structure in networks is intimately related to finding a concise description of the network in terms of its modules. This notion has been recently exploited by the map equation formalism [Rosvall and Bergstrom, Proc. Natl. Acad. Sci. USA 105, 1118 (2008)] through an information-theoretic description of the process of coding inter- and intracommunity transitions of a random walker in the network at stationarity. However, a thorough study of the relationship between the full Markov dynamics and the coding mechanism is still lacking. We show here that the original map coding scheme, which is both block-averaged and one-step, neglects the internal structure of the communities and introduces an upper scale, the "field-of-view" limit, in the communities it can detect. As a consequence, map is well tuned to detect clique-like communities but can lead to undesirable overpartitioning when communities are far from clique-like. We show that a signature of this behavior is a large compression gap: The map description length is far from its ideal limit. To address this issue, we propose a simple dynamic approach that introduces time explicitly into the map coding through the analysis of the weighted adjacency matrix of the time-dependent multistep transition matrix of the Markov process. The resulting Markov time sweeping induces a dynamical zooming across scales that can reveal (potentially multiscale) community structure above the field-of-view limit, with the relevant partitions indicated by a small compression gap.
authors.affiliation: Department of Mathematics, Imperial College London, London, United Kingdom. michael.schaub09@imperial.ac.uk
authors.forename: Michael T
authors.initials: MT
authors.lastname: Schaub
authors.forename: Renaud
authors.initials: R
authors.lastname: Lambiotte
authors.forename: Mauricio
authors.initials: M
authors.lastname: Barahona
mesh_terms: D000465:Algorithms; D000818:Animals; D044962:Data Compression; D006801:Humans; D008390:Markov Chains; D008954:Models, Biological; D015233:Models, Statistical; D012111:Residence Characteristics; D012944:Social Support