Phase transition in the detection of modules in sparse networks

Abstract

We present an asymptotically exact analysis of the problem of detecting communities in sparse random networks. Our results are also applicable to detection of functional modules, partitions, and colorings in noisy planted models. Using a cavity method analysis, we unveil a phase transition from a region where the original group assignment is undetectable to one where detection is possible. In some cases, the detectable region splits into an algorithmically hard region and an easy one. Our approach naturally translates into a practical algorithm for detecting modules in sparse networks, and learning the parameters of the underlying model.

4 pages, 4 figures

References in corpus (13)

• Finding and evaluating community structure in networks
• Community detection in graphs
• Cooperative Game Theory Approaches for Network Partitioning
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• The performance of modularity maximization in practical contexts
• The Bethe lattice spin glass revisited
• Mixture models and exploratory analysis in networks
• A Bayesian Approach to Network Modularity
• Community Detection as an Inference Problem
• Reconstruction on trees and spin glass transition
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• (Un)detectable cluster structure in sparse networks

Cited by in corpus (177)

• Machine learning and the physical sciences
• Community detection in networks: A user guide
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• The ground truth about metadata and community detection in networks
• Statistical physics of inference: Thresholds and algorithms
• Spectral methods for network community detection and graph partitioning
• Structure and inference in annotated networks
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Graph spectra and the detectability of community structure in networks
• A Classification for Community Discovery Methods in Complex Networks
• A network approach to topic models
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Learning Latent Block Structure in Weighted Networks
• Identification of core-periphery structure in networks
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Efficiently inferring community structure in bipartite networks
• Statistical physics-based reconstruction in compressed sensing
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• The many facets of community detection in complex networks
• Random graph models for dynamic networks
• Stochastic Block Models and Reconstruction
• Estimating the number of communities in a network
• Bayesian stochastic blockmodeling
• Community detection and graph partitioning
• Message passing on networks with loops
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Clustering Network Layers With the Strata Multilayer Stochastic Block Model
• Social significance of community structure: Statistical view
• Detecting communities using asymptotical Surprise
• Model Selection for Degree-corrected Block Models
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Spectral methods for the detection of network community structure: a comparative analysis
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• Reconstruction methods for networks: the case of economic and financial systems
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Multiway spectral community detection in networks
• Efficient method for estimating the number of communities in a network
• Generalized communities in networks
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Reconstructing networks with unknown and heterogeneous errors
• Benchmark model to assess community structure in evolving networks
• Eigenvalue Spectra of Modular Networks
• Finding One Community in a Sparse Graph
• Structural inference for uncertain networks
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Detectability of communities in heterogeneous networks
• Phase transitions in semisupervised clustering of sparse networks
• Scalable Text and Link Analysis with Mixed-Topic Link Models
• Spectra of networks containing short loops
• Spectra of random networks with arbitrary degrees
• Adapting the Stochastic Block Model to Edge-Weighted Networks
• Exploring the solution landscape enables more reliable network community detection
• Predicting human preferences using the block structure of complex social networks
• Community detection in networks without observing edges
• Spectra of random graphs with community structure and arbitrary degrees
• Community detection in networks with unequal groups
• Typology of phase transitions in Bayesian inference problems
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Community Detection with Side Information: Exact Recovery under the Stochastic Block Model
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Message passing methods on complex networks
• A testing based extraction algorithm for identifying significant communities in networks
• Information-theoretic thresholds for community detection in sparse networks
• A Replica Inference Approach to Unsupervised Multi-Scale Image Segmentation
• Sparse random graphs: regularization and concentration of the Laplacian
• Stochastic block model and exploratory analysis in signed networks
• Phase Transitions in Spectral Community Detection
• Finding network communities using modularity density
• Spectral Detection on Sparse Hypergraphs
• Cross-validation estimate of the number of clusters in a network
• A paradox in community detection
• Super-resolution community detection for layer-aggregated multilayer networks
• Universality of the stochastic block model
• Different approaches to community detection
• Fundamental limits to learning closed-form mathematical models from data
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• Community Detection via Random and Adaptive Sampling
• Finding communities in sparse networks
• Centrality metrics and localization in core-periphery networks
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Density Evolution in the Degree-correlated Stochastic Block Model
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Improving the performance of algorithms to find communities in networks
• Community Detection and Improved Detectability in Multiplex Networks
• Walk modularity and community structure in networks
• Dense Hebbian neural networks: a replica symmetric picture of supervised learning
• The Infinite Degree Corrected Stochastic Block Model
• A Map Equation with Metadata: Varying the Role of Attributes in Community Detection
• Subexponential-Time Algorithms for Sparse PCA
• Identifying multi-scale communities in networks by asymptotic surprise
• Spatial correlations in attribute communities
• Algorithmic detectability threshold of the stochastic block model
• Modularity and Projection of Bipartite Networks
• Fundamental problems in statistical physics XIV: Lecture on Machine Learning
• Phase Transitions in Community Detection: A Solvable Toy Model
• Comparative analysis on the selection of number of clusters in community detection
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Optimal Cluster Recovery in the Labeled Stochastic Block Model
• Community detection based on significance optimization in complex networks
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• Streaming, Memory Limited Algorithms for Community Detection
• The stability to instability transition in the structure of large scale networks
• Global disorder transition in the community structure of large-q Potts systems
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Spectral estimation of the percolation transition in clustered networks
• Multiple phases in modularity-based community detection
• Heterogeneous message passing for heterogeneous networks
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Free energies of Boltzmann Machines: self-averaging, annealed and replica symmetric approximations in the thermodynamic limit
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• Community detectability and structural balance dynamics in signed networks
• Finite size analysis of the detectability limit of the stochastic block model
• Normalized mutual information is a biased measure for classification and community detection
• Performance of a community detection algorithm based on semidefinite programming
• Gaussian-Spherical Restricted Boltzmann Machines
• Belief-Propagation Guided Monte-Carlo Sampling
• Limits and trade-offs of topological network robustness
• Cross-validation of correlation networks using modular structure
• Decoding communities in networks
• Unsupervised Community Detection with Modularity-Based Attention Model
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Communities in C.elegans connectome through the prism of non-backtracking walks
• Detectability thresholds of general modular graphs
• Spectral partitioning in equitable graphs
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• Critical behavior of the three-state random-field Potts model in three dimensions
• Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Local multiresolution order in community detection
• Democratic summary of public opinions in free-response surveys
• Matched bipartite block model with covariates
• Vulnerable Connectivity Caused by Local Communities in Spatial Networks
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Community Detection in networks by Dynamical Optimal Transport Formulation
• Generalised thresholding of hidden variable network models with scale-free property
• Learning Interpretable Collective Variables for Spreading Processes on Networks
• Consistency between ordering and clustering methods for graphs
• Bayesian reconstruction of memories stored in neural networks from their connectivity
• Minimum entropy stochastic block models neglect edge distribution heterogeneity
• Neural-prior stochastic block model
• Efficient inference in stochastic block models with vertex labels
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation
• Comprehensive spectral approach for community structure analysis on complex networks
• Stochastic fluctuations and the detectability limit of network communities
• NISQ-ready community detection based on separation-node identification
• Side Information in the Binary Stochastic Block Model: Exact Recovery
• Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks
• Confidence sets in a sparse stochastic block model with two communities of unknown sizes
• Clustering in Block Markov Chains
• Local Algorithms for Block Models with Side Information
• Router-level community structure of the Internet Autonomous Systems
• Large deviations of connected components in the stochastic block model
• The Stochastic Replica Approach to Machine Learning: Stability and Parameter Optimization
• Revisiting Spectral Graph Clustering with Generative Community Models
• Community Detection Algorithm Combining Stochastic Block Model and Attribute Data Clustering
• Single-trajectory map equation
• Uniqueness of communities in regular stochastic block models
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• An approximation for return time distributions of random walks on sparse networks
• Thermodynamics of the Minimum Description Length on Community Detection
• Phase Transitions in Spectral Community Detection of Large Noisy Networks
• Fault Tolerance of Random Graphs with respect to Connectivity: Mean-field Approximation for Semi-dense Random Graphs
• Reinventing the Triangles: Rule of Thumb for Assessing Detectability
• Error-Correcting Decoders for Communities in Networks
• Detectability threshold in weighted modular networks
• Uncertainty quantification and testing in a stochastic block model with two unequal communities