Computational Lower Bounds for Community Detection on Random Graphs

Abstract

This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph $\mathcal{G}(N,q)$, where the edge probability within the community exceeds $q$ by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size $N$ grows and the graph becomes sparser according to $q=N^{-\alpha }$, there exists a critical value of $\alpha =\frac{2}{3}$, below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest $K$-subgraph.

28 pages

References in corpus (5)

• Community detection in graphs
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Computational barriers in minimax submatrix detection
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time

Cited by in corpus (9)

• Statistical physics of inference: Thresholds and algorithms
• Finding One Community in a Sparse Graph
• Statistical and computational trade-offs in estimation of sparse principal components
• Computational Barriers to Estimation from Low-Degree Polynomials
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E|{\log }^{\ast }|V|)$ Time
• Detecting a planted community in an inhomogeneous random graph
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning