Narrow scope for resolution-limit-free community detection

Abstract

Detecting communities in large networks has drawn much attention over the years. While modularity remains one of the more popular methods of community detection, the so-called resolution limit remains a significant drawback. To overcome this issue, it was recently suggested that instead of comparing the network to a random null model, as is done in modularity, it should be compared to a constant factor. However, it is unclear what is meant exactly by "resolution-limit-free", that is, not suffering from the resolution limit. Furthermore, the question remains what other methods could be classified as resolution-limit-free. In this paper we suggest a rigorous definition and derive some basic properties of resolution-limit-free methods. More importantly, we are able to prove exactly which class of community detection methods are resolution-limit-free. Furthermore, we analyze which methods are not resolution-limit-free, suggesting there is only a limited scope for resolution-limit-free community detection methods. Finally, we provide such a natural formulation, and show it performs superbly.

References in corpus (27)

• Fast unfolding of communities in large networks
• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Functional cartography of complex metabolic networks
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Community detection algorithms: a comparative analysis
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Community structure in directed networks
• The performance of modularity maximization in practical contexts
• An information-theoretic framework for resolving community structure in complex networks
• Modularity and community detection in bipartite networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Community detection in networks with positive and negative links
• Geographical dispersal of mobile communication networks
• 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
• Uncovering space-independent communities in spatial networks
• Assessing the relevance of node features for network structure
• Local resolution-limit-free Potts model for community detection
• Limited resolution in complex network community detection with Potts model approach
• Finding instabilities in the community structure of complex networks
• Partitioning and modularity of graphs with arbitrary degree distribution
• Note on the equivalence of the label propagation method of community detection and a Potts model approach

Cited by in corpus (70)

• From Louvain to Leiden: guaranteeing well-connected communities
• Community detection in networks: A user guide
• A smart local moving algorithm for large-scale modularity-based community detection
• Limits of modularity maximization in community detection
• Robust Detection of Dynamic Community Structure in Networks
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Community Detection via Maximization of Modularity and Its Variants
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Significant Scales in Community Structure
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Faster unfolding of communities: speeding up the Louvain algorithm
• Detecting communities using asymptotical Surprise
• Surprise maximization reveals the community structure of complex networks
• Node and layer eigenvector centralities for multiplex networks
• Exploring the limits of community detection strategies in complex networks
• Estimating the resolution limit of the map equation in community detection
• The stability of a graph partition: A dynamics-based framework for community detection
• Hierarchical multiresolution method to overcome the resolution limit in complex networks
• Community structure: A comparative evaluation of community detection methods
• Magnetic eigenmaps for community detection in directed networks
• Graph-based data clustering via multiscale community detection
• Large network community detection by fast label propagation
• Correlation-based feature selection to identify functional dynamics in proteins
• Multiscale dynamical embeddings of complex networks
• Network community detection using modularity density measures
• Axioms for graph clustering quality functions
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Finding network communities using modularity density
• Granularity of algorithmically constructed publication-level classifications of research publications: Identification of topics
• Universality of the stochastic block model
• Hierarchical community structure in networks
• Granularity of algorithmically constructed publication-level classifications of research publications: Identification of specialties
• SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization
• Community detection in networks via nonlinear modularity eigenvectors
• GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting
• Label propagation for clustering
• An algebraic analysis of the graph modularity
• Asymptotic resolution bounds of generalized modularity and multi-scale community detection
• Learning protein-ligand unbinding pathways via single-parameter community detection
• Community detection based on significance optimization in complex networks
• The stability to instability transition in the structure of large scale networks
• Global disorder transition in the community structure of large-q Potts systems
• Total variation based community detection using a nonlinear optimization approach
• Berlin: A Quantitative View of the Structure of Institutional Scientific Collaborations
• Discovering Communication Pattern Shifts in Large-Scale Labeled Networks using Encoder Embedding and Vertex Dynamics
• Multiresolution Consensus Clustering in Networks
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Generalized Markov stability of network communities
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• The Hyperspherical Geometry of Community Detection: Modularity as a Distance
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• An algorithm for network community structure determination by surprise
• Automatic exploration of structural regularities in networks
• Local multiresolution order in community detection
• A Synthetic Network Generator for Covert Network Analytics
• Resolution limit revisited: community detection using generalized modularity density
• An Efficient Quadratic Penalty Method for a Class of Graph Clustering Problems
• How to interpret algorithmically constructed topical structures of research specialties? A case study comparing an internal and an external mapping of the topical structure of invasion biology
• Router-level community structure of the Internet Autonomous Systems
• Bad Communities with High Modularity
• Normalization of direct citations in publication-level networks: Evaluation of six approaches
• From Leiden to Pleasure Island: The Constant Potts Model for Community Detection as a Hedonic Game
• Structure of a media co-occurrence network
• CellSegmenter: unsupervised representation learning and instance segmentation of modular images
• Community Detection in Energy Networks based on Energy Self-Sufficiency and Dynamic Flexibility Activation
• Absence of a resolution limit in in-block nestedness
• Community Detection by a Riemannian Projected Proximal Gradient Method
• More sophisticated is not always better: comparison of similarity measures for unsupervised learning of pathways in biomolecular simulations
• GPU-Accelerated Multilevel Graph Clustering: A Parallel Perspective on Louvain and Leiden