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 Erdos-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 = 23, 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.

Tasks

Reproductions