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\H{o}s-R\'enyi 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.
Cite
Text
Hajek et al. "Computational Lower Bounds for Community Detection on Random Graphs." Annual Conference on Computational Learning Theory, 2015.Markdown
[Hajek et al. "Computational Lower Bounds for Community Detection on Random Graphs." Annual Conference on Computational Learning Theory, 2015.](https://mlanthology.org/colt/2015/hajek2015colt-computational/)BibTeX
@inproceedings{hajek2015colt-computational,
title = {{Computational Lower Bounds for Community Detection on Random Graphs}},
author = {Hajek, Bruce E. and Wu, Yihong and Xu, Jiaming},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2015},
pages = {899-928},
url = {https://mlanthology.org/colt/2015/hajek2015colt-computational/}
}