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 (13)

• Cooperative Game Theory Approaches for Network Partitioning
• Benchmark graphs for testing community detection algorithms
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• 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
• A Bayesian Approach to Network Modularity
• Community Detection as an Inference Problem
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• (Un)detectable cluster structure in sparse networks

Cited by in corpus (296)

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