Sign inSign up
Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery thumbnail
slide-image
Pause
Mute
Subtitles not available
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery

Published on Aug 20, 20151675 Views

Peter Chin

In this paper, we present and analyze a simple and robust spectral algorithm for the stochastic block model with $k$ blocks, for any $k$ fixed. Our algorithm works with graphs having constant edge den

COLT 2015 - Paris

Related categories

Active LearningComputational Learning TheoryOn-line LearningReinforcement LearningSemi-supervised Learning

Chapter list

Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery00:00
Overview00:08
Stochastic Block Model: SBM(n, k, a, b) - 100:28
Stochastic Block Model: SBM(n, k, a, b) - 200:46
γ-correct recovery01:11
Related work01:30
Results: 2-block case01:50
Example: 2-block case before clustering02:23
Example: 2-block case after clustering02:57
Results: k-block case03:02
Proof Idea: 2-block case - 103:36
Proof Idea: 2-block case - 203:44
Proof Idea: 2-block case - 303:54
Proof Idea: 2-block case - 403:57
Proof Idea: 2-block case - 503:59
Spectral part04:01