mlsanityData to 7 Oct 2026

Computational Lower Bounds for Community Detection on Random Graphs

arXiv 1406.6625 ↗First posted 25 Jun 2014math.ST cs.CC stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

This paper studies the problem of detecting the presence of a small dense community planted in a large ErdHos-R'enyi random graph 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-α, there exists a critical value of α = frac23, 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.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Jun 2014.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 4; 2022: 5; 2023: 7; 2024: 2; 2025: 3.

21 papers.

Sort:

  1. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  2. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  3. 2023Detection of Dense Subhypergraphs by Low-Degree Polynomialscited by 7
  4. 2022Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomialscited by 6
  5. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  6. 2022Is it easier to count communities than find them?cited by 4
  7. 2023Detection-Recovery Gap for Planted Dense Cyclescited by 4
  8. 2021Random Subgraph Detection Using Queriescited by 3
  9. 2021Inferring Hidden Structures in Random Graphscited by 2
  10. 2022Community Recovery in the Geometric Block Modelcited by 2
  11. 2023Planted Bipartite Graph Detectioncited by 2
  12. 2023Bayes optimal learning in high-dimensional linear regression with network side informationcited by 2
9 more
  1. 2022Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learningcited by 1
  2. 2023Phase transition for detecting a small community in a large networkcited by 1
  3. 2023Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embeddingcited by 1
  4. 2024Information-Theoretic Thresholds for Planted Dense Cyclescited by 1
  5. 2025Optimal community detection in dense bipartite graphscited by 1
  6. 2021Logspace Reducibility From Secret Leakage Planted Cliquecited by 0
  7. 2024Computationally efficient reductions between some statistical modelscited by 0
  8. 2025Robust Detection of Planted Subgraphs in Semi-Random Modelscited by 0
  9. 2025Statistical and computational challenges in rankingcited by 0