Computational lower bounds for community detection on random graphs

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.