Computational Lower Bounds for Community Detection on Random Graphs

Bruce Hajek, Yihong Wu, Jiaming Xu
Proceedings of The 28th Conference on Learning Theory, PMLR 40:899-928, 2015.

Abstract

This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph \calG(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 α= \frac23, 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 this Paper

BibTeX
@InProceedings{pmlr-v40-Hajek15, title = {Computational Lower Bounds for Community Detection on Random Graphs}, author = {Hajek, Bruce and Wu, Yihong and Xu, Jiaming}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {899--928}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Hajek15.pdf}, url = {https://proceedings.mlr.press/v40/Hajek15.html}, abstract = {This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph \calG(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 α= \frac23, 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. } }
Endnote
%0 Conference Paper %T Computational Lower Bounds for Community Detection on Random Graphs %A Bruce Hajek %A Yihong Wu %A Jiaming Xu %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Hajek15 %I PMLR %P 899--928 %U https://proceedings.mlr.press/v40/Hajek15.html %V 40 %X This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph \calG(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 α= \frac23, 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.
RIS
TY - CPAPER TI - Computational Lower Bounds for Community Detection on Random Graphs AU - Bruce Hajek AU - Yihong Wu AU - Jiaming Xu BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Hajek15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 899 EP - 928 L1 - http://proceedings.mlr.press/v40/Hajek15.pdf UR - https://proceedings.mlr.press/v40/Hajek15.html AB - This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph \calG(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 α= \frac23, 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. ER -
APA
Hajek, B., Wu, Y. & Xu, J.. (2015). Computational Lower Bounds for Community Detection on Random Graphs. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:899-928 Available from https://proceedings.mlr.press/v40/Hajek15.html.

Related Material