Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms

Abstract

We consider the problem of community detection in the Stochastic Block Model with a finite number $K$ of communities of sizes linearly growing with the network size $n$. This model consists in a random graph such that each pair of vertices is connected independently with probability $p$ within communities and $q$ across communities. One observes a realization of this random graph, and the objective is to reconstruct the communities from this observation. We show that under spectral algorithms, the number of misclassified vertices does not exceed $s$ with high probability as $n$ grows large, whenever $pn=\omega (1)$, $s=o(n)$ and \begin{equation*} \lim\inf_{n\to\infty} {n(α_1 p+α_2 q-(α_1 + α_2)p^{\frac{α_1}{α_1 + α_2}}q^{\frac{α_2}{α_1 + α_2}})\over \log (\frac{n}{s})} >1,\quad\quad(1) \end{equation*} where ${\alpha }_1$ and ${\alpha }_2$ denote the (fixed) proportions of vertices in the two smallest communities. In view of recent work by Abbe et al. and Mossel et al., this establishes that the proposed spectral algorithms are able to exactly recover communities whenever this is at all possible in the case of networks with two communities with equal sizes. We conjecture that condition (1) is actually necessary to obtain less than $s$ misclassified vertices asymptotically, which would establish the optimality of spectral method in more general scenarios.

References in corpus (4)

• Phase transition in the detection of modules in sparse networks
• Stochastic Block Models and Reconstruction
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Community detection thresholds and the weak Ramanujan property

Cited by in corpus (29)

• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Density Evolution in the Degree-correlated Stochastic Block Model
• Recovering communities in the general stochastic block model without knowing the parameters
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• Optimal Cluster Recovery in the Labeled Stochastic Block Model
• Optimal Bipartite Network Clustering
• Detecting Latent Communities in Network Formation Models
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E|{\log }^{\ast }|V|)$ Time
• Adjusted chi-square test for degree-corrected block models
• Strong Consistency, Graph Laplacians, and the Stochastic Block Model
• Non-Asymptotic Chernoff Lower Bound and Its Application to Community Detection in Stochastic Block Model
• Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method
• Multi-Frequency Joint Community Detection and Phase Synchronization
• Clustering in Block Markov Chains
• Local Algorithms for Block Models with Side Information
• Exponential error rates of SDP for block models: Beyond Grothendieck's inequality
• Almost exact recovery in noisy semi-supervised learning
• Pair-Matching: Links Prediction with Adaptive Queries
• Partial recovery bounds for clustering with the relaxed $K$means
• Combinatorial-Probabilistic Trade-Off: Community Properties Test in the Stochastic Block Models
• Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
• Exact Recovery in the General Hypergraph Stochastic Block Model