Sign inSign up
Computational Lower Bounds for Community Detection on Random Graphs thumbnail
Pause
Mute
Subtitles not available
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Computational Lower Bounds for Community Detection on Random Graphs

Published on Aug 20, 20151670 Views

Bruce Hajek

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

COLT 2015 - Paris

Related categories

Active LearningComputational Learning TheoryOn-line LearningReinforcement LearningSemi-supervised Learning

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