Computational Lower Bounds for Community Detection on Random Graphs
This provides computational lower bounds for community detection, impacting graph analysis and algorithm design, but it is incremental as it builds on planted clique hardness assumptions.
The paper tackles the problem of detecting a small dense community in a random graph, showing that there is a critical sparsity threshold (α=2/3) where computationally intensive methods outperform efficient ones below it, and a linear-time method is optimal above it.
This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi 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^{-α}$, there exists a critical value of $α= \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.