0.25
0.5
0.75
1.25
1.5
1.75
2
Computational Lower Bounds for Community Detection on Random Graphs
Published on Aug 20, 20151666 Views
This paper studies the problem of detecting the presence of a small dense community planted in a large Erd\H{o}s-R\'enyi random graph $\calG(N,q)$, where the edge probability within the community exce
Related categories
Chapter list
Computational Lower Bounds for Community Detection on Random Graphs00:00
Community detection in networks00:01
Stochastic block model (Planted partition model) - 100:03
Stochastic block model (Planted partition model) - 200:22
Stochastic block model (Planted partition model) - 300:31
Stochastic block model (Planted partition model) - 400:37
This paper focuses on r = 1: a single community00:52
Planted clique hardness hypothesis01:28
Main result: Hardness for detecting a single cluster - 102:32
Main result: Hardness for detecting a single cluster - 202:42
Main result: Hardness for recovering a single cluster - 102:55
Main result: Hardness for recovering a single cluster - 203:05