Local resolution-limit-free Potts model for community detection

Abstract

We report on an exceptionally accurate spin-glass-type Potts model for community detection. With a simple algorithm, we find that our approach is at least as accurate as the best currently available algorithms and robust to the effects of noise. It is also competitive with the best currently available algorithms in terms of speed and size of solvable systems. We find that the computational demand often exhibits superlinear scaling L^1.3 where L is the number of edges in the system, and we have applied the algorithm to synthetic systems as large as 40x10^6 nodes and over 1x10^9 edges. A previous stumbling block encountered by popular community detection methods is the so-called "resolution limit." Being a "local" measure of community structure, our Potts model is free from this resolution-limit effect, and it further remains a local measure on weighted and directed graphs. We also address the mitigation of resolution-limit effects for two other popular Potts models.

16 pages, 12 figures; title change for Physical Review E, minor editing, updated references

References in corpus (27)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Community detection algorithms: a comparative analysis
• Statistical Mechanics of Community Detection
• Detecting the overlapping and hierarchical community structure of complex networks
• The performance of modularity maximization in practical contexts
• Community detection in networks with positive and negative links
• Analysis of the structure of complex networks at different resolution levels
• Detecting network communities by propagating labels under constraints
• Size reduction of complex networks preserving modularity
• Multiresolution community detection for megascale networks by information-based replica correlations
• A sequential algorithm for fast clique percolation
• Community Detection as an Inference Problem
• Limited resolution in complex network community detection with Potts model approach
• Immunization of networks with community structure
• Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007--2008 credit crisis
• Community Detection in Complex Networks by Dynamical Simplex Evolution
• Detecting modules in dense weighted networks with the Potts method
• Effect of size heterogeneity on community identification in complex networks
• Finding mesoscopic communities in sparse networks

Cited by in corpus (59)

• Community detection in graphs
• Community detection in networks: A user guide
• Limits of modularity maximization in community detection
• Narrow scope for resolution-limit-free community detection
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Robust network community detection using balanced propagation
• Faster unfolding of communities: speeding up the Louvain algorithm
• Detecting communities using asymptotical Surprise
• Surprise maximization reveals the community structure of complex networks
• Estimating the resolution limit of the map equation in community detection
• Exploring the limits of community detection strategies in complex networks
• Assessing the structural heterogeneity of supercooled liquids through community inference
• The stability of a graph partition: A dynamics-based framework for community detection
• Hierarchical multiresolution method to overcome the resolution limit in complex networks
• Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations
• Graph-based data clustering via multiscale community detection
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Community Detection in Complex Networks Using Density-based Clustering Algorithm
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Limitation of multi-resolution methods in community detection
• Network community detection using modularity density measures
• A Replica Inference Approach to Unsupervised Multi-Scale Image Segmentation
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Universality of the stochastic block model
• Improving the performance of algorithms to find communities in networks
• SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization
• A General Framework for Complex Network-Based Image Segmentation
• Cell assembly dynamics of sparsely-connected inhibitory networks: a simple model for the collective activity of striatal projection neurons
• Community detection in networks via nonlinear modularity eigenvectors
• Identifying multi-scale communities in networks by asymptotic surprise
• Coupled Graphs and Tensor Factorization for Recommender Systems and Community Detection
• Label propagation for clustering
• Community detection based on significance optimization in complex networks
• Stochastic Replica Voting Machine Prediction of Stable Cubic and Double Perovskite Materials and Binary Alloys
• Global disorder transition in the community structure of large-q Potts systems
• Finding overlapping communities in networks using evolutionary method
• The stability to instability transition in the structure of large scale networks
• Unfolding network communities by combining defensive and offensive label propagation
• Automatic Segmentation of Fluorescence Lifetime Microscopy Images of Cells Using Multi-Resolution Community Detection
• Modeling power grids
• Augmentative Message Passing for Traveling Salesman Problem and Graph Partitioning
• Generalized network community detection
• Community detection in weighted brain connectivity networks beyond the resolution limit
• Automatic exploration of structural regularities in networks
• Local multiresolution order in community detection
• An algorithm for network community structure determination by surprise
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Comparison and Benchmark of Graph Clustering Algorithms
• Resolution limit revisited: community detection using generalized modularity density
• An Efficient Quadratic Penalty Method for a Class of Graph Clustering Problems
• Phase transition for parameter learning of Hidden Markov Models
• Non-equilibrium Dynamics and Phase Transitions in Potts model and Interacting Ehrenfest urn model
• Spiking label propagation for community detection
• Agglomerative Likelihood Clustering
• Unsupervised Community Detection with a Potts Model Hamiltonian, an Efficient Algorithmic Solution, and Applications in Digital Pathology
• Analysis of Social Group Dynamics