Computational lower bounds for community detection on random graphs

Bruce Hajek, Yihong Wu, Jiaming Xu

Research output: Contribution to journalConference articlepeer-review


This paper studies the problem of detecting the presence of a small dense community planted in a large Erdos-Rényi 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 α = 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.

Original languageEnglish (US)
JournalJournal of Machine Learning Research
Issue number2015
StatePublished - 2015
Event28th Conference on Learning Theory, COLT 2015 - Paris, France
Duration: Jul 2 2015Jul 6 2015

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Computational lower bounds for community detection on random graphs'. Together they form a unique fingerprint.

Cite this