Information-theoretic thresholds for community detection in sparse networks

Abstract

We give upper and lower bounds on the information-theoretic threshold for community detection in the stochastic block model. Specifically, let $k$ be the number of groups, $d$ be the average degree, the probability of edges between vertices within and between groups be $c_{\mathrm{in}}/n$ and $c_{\mathrm{out}}/n$ respectively, and let $\lambda =(c_{\mathrm{in}}-c_{\mathrm{out}})/(kd)$. We show that, when $k$ is large, and $\lambda =O(1/k)$, the critical value of $d$ at which community detection becomes possible -- in physical terms, the condensation threshold -- is \[ d_c = Θ\!\left( \frac{\log k}{k λ^2} \right) \, , \] with tighter results in certain regimes. Above this threshold, we show that the only partitions of the nodes into $k$ groups are correlated with the ground truth, giving an exponential-time algorithm that performs better than chance -- in particular, detection is possible for $k\ge 5$ in the disassortative case $\lambda <0$ and for $k\ge 11$ in the assortative case $\lambda >0$. (Similar upper bounds were obtained independently by Abbe and Sandon.) Below this threshold, we use recent results of Neeman and Netrapalli (who generalized arguments of Mossel, Neeman, and Sly) to show that no algorithm can label the vertices better than chance, or even distinguish the block model from an Erdős-Rényi random graph with high probability. We also rely on bounds on certain functions of doubly stochastic matrices due to Achlioptas and Naor; indeed, our lower bound on $d_c$ is the second moment lower bound on the $k$-colorability threshold for random graphs with a certain effective degree.

References in corpus (5)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase transition in the detection of modules in sparse networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Community detection in networks with unequal groups
• Global and Local Information in Clustering Labeled Block Models

Cited by in corpus (19)

• Information-theoretic thresholds from the cavity method
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Testing for Global Network Structure Using Small Subgraph Statistics
• Charting the replica symmetric phase
• Optimal hypothesis testing for stochastic block models with growing degrees
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Testing Community Structures for Hypergraphs
• Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization
• Optimal link prediction with matrix logistic regression
• Inference and mutual information on random factor graphs
• Non-linear Log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• Pair-Matching: Links Prediction with Adaptive Queries
• The non-tightness of the reconstruction threshold of a 4 states symmetric model with different in-block and out-block mutations
• Modularity of Erdős-Rényi random graphs
• Robust Correlation Clustering with Asymmetric Noise