Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit

Abstract

In recent years, there has been a surge of interest in community detection algorithms for complex networks. A variety of computational heuristics, some with a long history, have been proposed for the identification of communities or, alternatively, of good graph partitions. In most cases, the algorithms maximize a particular objective function, thereby finding the `right' split into communities. Although a thorough comparison of algorithms is still lacking, there has been an effort to design benchmarks, i.e., random graph models with known community structure against which algorithms can be evaluated. However, popular community detection methods and benchmarks normally assume an implicit notion of community based on clique-like subgraphs, a form of community structure that is not always characteristic of real networks. Specifically, networks that emerge from geometric constraints can have natural non clique-like substructures with large effective diameters, which can be interpreted as long-range communities. In this work, we show that long-range communities escape detection by popular methods, which are blinded by a restricted `field-of-view' limit, an intrinsic upper scale on the communities they can detect. The field-of-view limit means that long-range communities tend to be overpartitioned. We show how by adopting a dynamical perspective towards community detection (Delvenne et al. (2010) PNAS:107: 12755-12760; Lambiotte et al. (2008) arXiv:0812.1770), in which the evolution of a Markov process on the graph is used as a zooming lens over the structure of the network at all scales, one can detect both clique- or non clique-like communities without imposing an upper scale to the detection. Consequently, the performance of algorithms on inherently low-diameter, clique-like benchmarks may not always be indicative of equally good results in real networks with local, sparser connectivity.

20 pages, 6 figures

References in corpus (20)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Statistical physics of social dynamics
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• An information-theoretic framework for resolving community structure in complex networks
• Limits of modularity maximization in community detection
• Sustaining the Internet with Hyperbolic Mapping
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Narrow scope for resolution-limit-free community detection
• Robustness of the European power grids under intentional attack
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Multi-scale Modularity in Complex Networks
• Protein multi-scale organization through graph partitioning and robustness analysis: Application to the myosin-myosin light chain interaction
• Effect of size heterogeneity on community identification in complex networks

Cited by in corpus (56)

• Random walks and diffusion on networks
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Topological strata of weighted complex networks
• Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
• The many facets of community detection in complex networks
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Multi-scale community organization of the human structural connectome and its relationship with resting-state functional connectivity
• Detecting communities using asymptotical Surprise
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Estimating the resolution limit of the map equation in community detection
• Flow-based network analysis of the Caenorhabditis elegans connectome
• 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
• Emergence of slow-switching assemblies in structured neuronal networks
• Efficient community detection of network flows for varying Markov times and bipartite networks
• Multi-scale analysis of the European airspace using network community detection
• Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution
• Diffusion geometry unravels the emergence of functional clusters in collective phenomena
• Graph-based data clustering via multiscale community detection
• Revealing cell assemblies at multiple levels of granularity
• Multiscale dynamical embeddings of complex networks
• Using higher-order Markov models to reveal flow-based communities in networks
• A Biased Review of Biases in Twitter Studies on Political Collective Action
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Uncovering allosteric pathways in caspase-1 with Markov transient analysis and multiscale community detection
• From Free Text to Clusters of Content in Health Records: An Unsupervised Graph Partitioning Approach
• Different approaches to community detection
• Flow stability for dynamic community detection
• SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization
• Modularity and the spread of perturbations in complex dynamical systems
• Mapping flows on sparse networks with missing links
• Scale-dependent measure of network centrality from diffusion dynamics
• Geometric Multiscale Community Detection: Markov Stability and Vector Partitioning
• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• Modular decomposition of protein structure using community detection
• Multiscale mobility patterns and the restriction of human movement
• Multiresolution Consensus Clustering in Networks
• PyGenStability: Multiscale community detection with generalized Markov Stability
• Cycle flow based module detection in directed recurrence networks
• State aggregations in Markov chains and block models of networks
• Multiplex Markov Chains: Convection Cycles and Optimality
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Entrograms and coarse graining of dynamics on complex networks
• Identifying robust features of community structure in complex networks
• Benchmarking community detection methods on social media data
• Making Communities Show Respect for Order
• Community Detection with the Map Equation and Infomap: Theory and Applications
• The Atlas for the Aspiring Network Scientist
• Extracting information from free text through unsupervised graph-based clustering: an application to patient incident records
• From Text to Topics in Healthcare Records: An Unsupervised Graph Partitioning Methodology
• When Does Bottom-up Beat Top-down in Hierarchical Community Detection?
• Low-rank Similarity Measure for Role Model Extraction
• Dynamics of Cluster Synchronisation in Modular Networks: Implications for Structural and Functional Networks
• Multiscale Community Mining in Networks Using Spectral Graph Wavelets
• Multiscale methods for signal selection in single-cell data
• Graph clustering in industrial networks