Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications

Abstract

In this paper we extend our previous work on the stochastic block model, a commonly used generative model for social and biological networks, and the problem of inferring functional groups or communities from the topology of the network. We use the cavity method of statistical physics to obtain an asymptotically exact analysis of the phase diagram. We describe in detail properties of the detectability/undetectability phase transition and the easy/hard phase transition for the community detection problem. Our analysis translates naturally into a belief propagation algorithm for inferring the group memberships of the nodes in an optimal way, i.e., that maximizes the overlap with the underlying group memberships, and learning the underlying parameters of the block model. Finally, we apply the algorithm to two examples of real-world networks and discuss its performance.

Typos in eq. (40) on p. 13 fixed

References in corpus (26)

• Finding and evaluating community structure in networks
• Community detection in graphs
• Cooperative Game Theory Approaches for Network Partitioning
• Benchmark graphs for testing community detection algorithms
• Community detection algorithms: a comparative analysis
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Community detection in complex networks using Extremal Optimization
• The performance of modularity maximization in practical contexts
• The Bethe lattice spin glass revisited
• Missing and spurious interactions and the reconstruction of complex networks
• Mixture models and exploratory analysis in networks
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase transition in the detection of modules in sparse networks
• An efficient and principled method for detecting communities in networks
• Phase Transitions in the Coloring of Random Graphs
• 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
• A ferromagnet with a glass transition
• The Nishimori line and Bayesian Statistics
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• (Un)detectable cluster structure in sparse networks
• Robust reconstruction on trees is determined by the second eigenvalue
• Belief propagation for graph partitioning

Cited by in corpus (299)

• Machine learning and the physical sciences
• Spectral redemption: clustering sparse networks
• Statistical physics of inference: Thresholds and algorithms
• Consistency of spectral clustering in stochastic block models
• Convolutional Neural Network Architectures for Signals Supported on Graphs
• Consistency of community detection in networks under degree-corrected stochastic block models
• Pseudo-likelihood methods for community detection in large sparse networks
• 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
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• 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
• 20 years of network community detection
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Spectral entropies as information-theoretic tools for complex network comparison
• Multilayer Brain Networks
• Quantum Machine Learning for Chemistry and Physics
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Network reconstruction and community detection from dynamics
• Stochastic Block Models and Reconstruction
• Entropy of stochastic blockmodel ensembles
• A goodness-of-fit test for stochastic block models
• Bayesian stochastic blockmodeling
• Supervised Community Detection with Line Graph Neural Networks
• Social significance of community structure: Statistical view
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Phase Transitions in Semidefinite Relaxations
• Extremal Cuts of Sparse Random Graphs
• 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
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Clustering Partially Observed Graphs via Convex Optimization
• Information-theoretic thresholds from the cavity method
• Consistent estimation of dynamic and multi-layer block models
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• A Clarified Typology of Core-Periphery Structure in Networks
• A message-passing approach for recurrent-state epidemic models on networks
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Generalized communities in networks
• Evaluating accuracy of community detection using the relative normalized mutual information
• Statistical inference of assortative community structures
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Community Detection in Large Hypergraphs
• Community Detection in the Labelled Stochastic Block Model
• Approximate fast graph Fourier transforms via multi-layer sparse approximations
• Block Models and Personalized PageRank
• Finding One Community in a Sparse Graph
• Consistencies and inconsistencies between model selection and link prediction in networks
• Message-passing algorithms for synchronization problems over compact groups
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Consistency of community structure in complex networks
• Local dominance unveils clusters in networks
• Structural inference for uncertain networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Disentangling bipartite and core-periphery structure in financial networks
• Random Graph Modeling: A survey of the concepts
• Phase transitions in semisupervised clustering of sparse networks
• Compressive Spectral Clustering
• Scalable Text and Link Analysis with Mixed-Topic Link Models
• Belief propagation for networks with loops
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• A Survey on Theoretical Advances of Community Detection in Networks
• A message-passing approach for threshold models of behavior in networks
• Improved Graph Clustering
• Merge-split Markov chain Monte Carlo for community detection
• Typology of phase transitions in Bayesian inference problems
• Community detection in networks with unequal groups
• Community Detection with Side Information: Exact Recovery under the Stochastic Block Model
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Phase transition in the recoverability of network history
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Belief propagation, robust reconstruction and optimal recovery of block models
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Network structure, metadata and the prediction of missing nodes and annotations
• Classifying Patents Based on their Semantic Content
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Sparse random graphs: regularization and concentration of the Laplacian
• Revealing consensus and dissensus between network partitions
• Information-theoretic thresholds for community detection in sparse networks
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Clustering with Noisy Queries
• Disentangling homophily, community structure and triadic closure in networks
• Disordered Systems Insights on Computational Hardness
• Spectral Detection on Sparse Hypergraphs
• Charting the replica symmetric phase
• Optimal hypothesis testing for stochastic block models with growing degrees
• Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results
• Cross-validation estimate of the number of clusters in a network
• Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference
• Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
• Localized Linear Regression in Networked Data
• Annealing and replica-symmetry in Deep Boltzmann Machines
• Information-theoretic and algorithmic thresholds for group testing
• Computational Lower Bounds for Community Detection on Random Graphs
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• Hierarchical community structure in networks
• Mean-field theory of graph neural networks in graph partitioning
• Finding communities in sparse networks
• The organization of the interbank network and how ECB unconventional measures affected the e-MID overnight market
• Glassy nature of the hard phase in inference problems
• 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
• Centrality metrics and localization in core-periphery networks
• Community extraction in multilayer networks with heterogeneous community structure
• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
• Community Detection in Networks using Graph Distance
• Improving the performance of algorithms to find communities in networks
• Density Evolution in the Degree-correlated Stochastic Block Model
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Community Detection and Improved Detectability in Multiplex Networks
• Spectral Detection in the Censored Block Model
• Explicitly Linking Regional Activation and Function Connectivity: Community Structure of Weighted Networks with Continuous Annotation
• Non-Reconstructability in the Stochastic Block Model
• A unifying model for random matrix theory in arbitrary space dimensions
• Walk modularity and community structure in networks
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Aligning biological sequences by exploiting residue conservation and coevolution
• A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
• A connection between MAX $\kappa$-CUT and the inhomogeneous Potts spin glass in the large degree limit
• Optimal group testing
• The Infinite Degree Corrected Stochastic Block Model
• De-anonymization of Social Networks with Communities: When Quantifications Meet Algorithms
• Detection and localization of change points in temporal networks with the aid of stochastic block models
• Subexponential-Time Algorithms for Sparse PCA
• Community detection in the sparse hypergraph stochastic block model
• Algorithmic detectability threshold of the stochastic block model
• Recovering communities in the general stochastic block model without knowing the parameters
• Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
• Ergodicity in Stationary Graph Processes: A Weak Law of Large Numbers
• Spectral density of the non-backtracking operator
• Belief Propagation Neural Networks
• FADE: Fast and Asymptotically efficient Distributed Estimator for dynamic networks
• Community Detection in Degree-Corrected Block Models
• Self-isolation or borders closing: what prevents epidemic spreading better?
• Network mutual information measures for graph similarity
• Phase Transitions in Community Detection: A Solvable Toy Model
• Kernel k-Groups via Hartigan's Method
• Community detection with nodal information
• Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks
• Comparative analysis on the selection of number of clusters in community detection
• Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
• Scalable and Robust Community Detection with Randomized Sketching
• Clustering from Sparse Pairwise Measurements
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
• Active Learning for Community Detection in Stochastic Block Models
• Learning big Gaussian Bayesian networks: partition, estimation, and fusion
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• Parallel Tempering for the planted clique problem
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• On Detection and Structural Reconstruction of Small-World Random Networks
• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• Weighted Community Detection and Data Clustering Using Message Passing
• Regularized Stochastic Block Model for robust community detection in complex networks
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
• Community detection thresholds and the weak Ramanujan property
• The replica symmetric phase of random constraint satisfaction problems
• A theory of non-equilibrium local search on random satisfaction problems
• Exotic phase transitions of k-cores in clustered networks
• Multiple phases in modularity-based community detection
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Network Cross-Validation for Determining the Number of Communities in Network Data
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• A unified framework for spectral clustering in sparse graphs
• Detectability of the spectral method for sparse graph partitioning
• Optimal Bipartite Network Clustering
• Finite size analysis of the detectability limit of the stochastic block model
• An Underparametrized Deep Decoder Architecture for Graph Signals
• Optimization on Sparse Random Hypergraphs and Spin Glasses
• Optimal Rates for Community Estimation in the Weighted Stochastic Block Model
• Recovery thresholds in the sparse planted matching problem
• Link Prediction in Networks with Core-Fringe Data
• Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization
• Comparing Graph Clusterings: Set partition measures vs. Graph-aware measures
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Testing Community Structures for Hypergraphs
• A Tractable Fully Bayesian Method for the Stochastic Block Model
• Robustness of spectral methods for community detection
• Performance of a community detection algorithm based on semidefinite programming
• Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks
• Learning Communities in the Presence of Errors
• Asymptotic Theory of Eigenvectors for Random Matrices with Diverging Spikes
• Higher-Order Spectral Clustering under Superimposed Stochastic Block Model
• Bayes-optimal inference for spreading processes on random networks
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
• Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
• Decoding communities in networks
• How Many Communities Are There?
• Detectability thresholds of general modular graphs
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Relax, no need to round: integrality of clustering formulations
• Spectral partitioning in equitable graphs
• Neural Clustering Processes
• Communities in C.elegans connectome through the prism of non-backtracking walks
• The planted $k$-factor problem
• Metrics matter in community detection
• Optimal link prediction with matrix logistic regression
• Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
• Generative models for local network community detection
• Proof of a conjecture on the infinite dimension limit of a unifying model for random matrix theory
• Community Detection on Networks with Ricci Flow
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• Local multiresolution order in community detection
• Optimization of the dynamic transition in the continuous coloring problem
• Analyticity of the energy in an Ising spin glass with correlated disorder
• Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E|{\log }^{\ast }|V|)$ Time
• Cascade of Phase Transitions for Multi-Scale Clustering
• Adjusted chi-square test for degree-corrected block models
• Typical Performance of Approximation Algorithms for NP-hard Problems
• How social networks influence human behavior: An integrated latent space approach for differential social influence
• Geometric randomization of real networks with prescribed degree sequence
• Democratic summary of public opinions in free-response surveys
• Hypothesis testing for populations of networks
• Mutual Information for the Stochastic Block Model by the Adaptive Interpolation Method
• Inference and mutual information on random factor graphs
• Strong Consistency, Graph Laplacians, and the Stochastic Block Model
• Phase transitions and optimal algorithms for semi-supervised classifications on graphs: from belief propagation to graph convolution network
• Efficient inference in stochastic block models with vertex labels
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Stochastic fluctuations and the detectability limit of network communities
• The planted matching problem: Sharp threshold and infinite-order phase transition
• Soft happy colourings and community structure of networks
• Statistical mechanics of reputation systems in autonomous networks
• The Chromatic Number of Dense Random Block Graphs
• Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction
• Detectability of hierarchical communities in networks
• Neural-prior stochastic block model
• Multi-Frequency Joint Community Detection and Phase Synchronization
• Maximum Likelihood Estimation of Sparse Networks with Missing Observations
• Maximum Likelihood Latent Space Embedding of Logistic Random Dot Product Graphs
• The number of solutions for random regular NAE-SAT
• Statistical Limits of Convex Relaxations
• Minimum entropy stochastic block models neglect edge distribution heterogeneity
• Recognition Capabilities of a Hopfield Model with Auxiliary Hidden Neurons
• De-anonymizing Social Networks with Overlapping Community Structure
• Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Confidence sets in a sparse stochastic block model with two communities of unknown sizes
• Approximate Network Symmetry
• Percolation Threshold for Competitive Influence in Random Networks
• Found Graph Data and Planted Vertex Covers
• Community Detection with Node Attributes and its Generalization
• Side Information in the Binary Stochastic Block Model: Exact Recovery
• Large deviations of connected components in the stochastic block model
• A Time-Varying Network for Cryptocurrencies
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• Community Detection Using Slow Mixing Markov Models
• Fast Network Community Detection with Profile-Pseudo Likelihood Methods
• Robust Spectral Detection of Global Structures in the Data by Learning a Regularization
• Local Algorithms for Block Models with Side Information
• Community Detection Algorithm Combining Stochastic Block Model and Attribute Data Clustering
• Large Deviations of Semi-supervised Learning in the Stochastic Block Model
• Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay
• Corrected Bayesian information criterion for stochastic block models
• Thermodynamics of the Minimum Description Length on Community Detection
• Node Embedding via Word Embedding for Network Community Discovery
• Pair-Matching: Links Prediction with Adaptive Queries
• Uniqueness of communities in regular stochastic block models
• Phase transition for parameter learning of Hidden Markov Models
• Non-Convex Exact Community Recovery in Stochastic Block Model
• Learning Parametrised Graph Shift Operators
• Community Structure Recovery and Interaction Probability Estimation for Gossip Opinion Dynamics
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
• On role extraction for digraphs via neighbourhood pattern similarity
• Feature Learning and Network Structure from Noisy Node Activity Data
• Faster algorithms for the alignment of sparse correlated Erdös-Rényi random graphs
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• Active Community Detection with Maximal Expected Model Change
• EXIT Analysis for Community Detection
• Streaming Belief Propagation for Community Detection
• Error-Correcting Decoders for Communities in Networks
• Construction of simplicial complexes with prescribed degree-size sequences
• Regular Partitions and Their Use in Structural Pattern Recognition
• Planted matching problems on random hypergraphs
• Complex non-backtracking matrix for directed graphs
• Community Detection by $L_0$-penalized Graph Laplacian
• Leaders, Followers, and Community Detection
• Precise Error Rates for Computationally Efficient Testing
• Consistent Spectral Clustering of Network Block Models under Local Differential Privacy
• Uncertainty quantification and testing in a stochastic block model with two unequal communities
• Estimating Mixed-Memberships Using the Symmetric Laplacian Inverse Matrix
• Non-backtracking walks reveal compartments in sparse chromatin interaction networks
• Reconstruction in the Labeled Stochastic Block Model
• On Equivalence of Likelihood Maximization of Stochastic Block Model and Constrained Nonnegative Matrix Factorization
• Analysis of large sparse graphs using regular decomposition of graph distance matrices