Computational lower bounds for community detection on random graphs

Bruce Hajek, Yihong Wu, Jiaming Xu

Research output: Contribution to journalConference article

Abstract

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.

Original languageEnglish (US)
JournalJournal of Machine Learning Research
Volume40
Issue number2015
StatePublished - Jan 1 2015
Event28th Conference on Learning Theory, COLT 2015 - Paris, France
Duration: Jul 2 2015Jul 6 2015

Fingerprint

Community Detection
Random Graphs
Hardness
Lower bound
Computational complexity
Phase transitions
Sparse Graphs
Erdös
Clique
Critical value
Linear Time
Subgraph
Exceed
Computational Complexity
Phase Transition
Community
Graph in graph theory

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Cite this

Computational lower bounds for community detection on random graphs. / Hajek, Bruce; Wu, Yihong; Xu, Jiaming.

In: Journal of Machine Learning Research, Vol. 40, No. 2015, 01.01.2015.

Research output: Contribution to journalConference article

@article{3616f5e46c6b4eb6bba10a2c22ae70e0,
title = "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{\'e}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.",
author = "Bruce Hajek and Yihong Wu and Jiaming Xu",
year = "2015",
month = "1",
day = "1",
language = "English (US)",
volume = "40",
journal = "Journal of Machine Learning Research",
issn = "1532-4435",
publisher = "Microtome Publishing",
number = "2015",

}

TY - JOUR

T1 - Computational lower bounds for community detection on random graphs

AU - Hajek, Bruce

AU - Wu, Yihong

AU - Xu, Jiaming

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84984706970&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84984706970&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:84984706970

VL - 40

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

SN - 1532-4435

IS - 2015

ER -