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 (M. Rosvall and C.T. Bergstrom, PNAS, 105(4), pp.1118--1123, 2008) through an information-theoretic description of the process of coding inter- and intra-community 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.

10 pages, 6 figures

References in corpus (13)

• Modularity and community structure in networks
• Maps of random walks on complex networks reveal community structure
• Synchronization in complex networks
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• Finding statistically significant communities in networks
• Limits of modularity maximization in community detection
• Analysis of the structure of complex networks at different resolution levels
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Ranking and clustering of nodes in networks with smart teleportation
• Protein multi-scale organization through graph partitioning and robustness analysis: Application to the myosin-myosin light chain interaction
• Compression of Flow Can Reveal Overlapping-Module Organization in Networks

Cited by in corpus (28)

• Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Flow networks: A characterization of geophysical fluid transport
• Estimating the resolution limit of the map equation in community detection
• The stability of a graph partition: A dynamics-based framework for community detection
• Interest communities and flow roles in directed networks: the Twitter network of the UK riots
• Efficient community detection of network flows for varying Markov times and bipartite networks
• Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution
• Multiscale dynamical embeddings of complex networks
• Community detection in networks using graph embeddings
• Using higher-order Markov models to reveal flow-based communities in networks
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• From Free Text to Clusters of Content in Health Records: An Unsupervised Graph Partitioning Approach
• A novel framework to analyze complex network dynamics
• An integrative dynamical perspective for graph theory and the study of complex networks
• Comparing network covers using mutual information
• Multiresolution Consensus Clustering in Networks
• Mapping Flows on Bipartite Networks
• State aggregations in Markov chains and block models of networks
• Entrograms and coarse graining of dynamics on complex networks
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Identifying robust features of community structure in complex networks
• Modular decomposition of Markov chain: detecting hierarchical organization of pervasive communities
• Extracting information from free text through unsupervised graph-based clustering: an application to patient incident records
• The Atlas for the Aspiring Network Scientist
• Single-trajectory map equation
• Learning Resolution Parameters for Graph Clustering