Timezone: »
Poster
A NearlyLinear Time Algorithm for Exact Community Recovery in Stochastic Block Model
Peng Wang · Zirui Zhou · Anthony ManCho So
Thu Jul 16 07:00 AM  07:45 AM & Thu Jul 16 07:00 PM  07:45 PM (PDT) @ Virtual #None
Learning community structures in graphs that are randomly generated by stochastic block models (SBMs) has received much attention lately. In this paper, we focus on the problem of exactly recovering the communities in a binary symmetric SBM, where a graph of $n$ vertices is partitioned into two equalsized communities and the vertices are connected with probability $p = \alpha\log(n)/n$ within communities and $q = \beta\log(n)/n$ across communities for some $\alpha>\beta>0$. We propose a twostage iterative algorithm for solving this problem, which employs the power method with a random starting point in the firststage and turns to a generalized power method that can identify the communities in a finite number of iterations in the secondstage. It is shown that for any fixed $\alpha$ and $\beta$ such that $\sqrt{\alpha}  \sqrt{\beta} > \sqrt{2}$, which is known to be the informationtheoretical limit for exact recovery, the proposed algorithm exactly identifies the underlying communities in $\tilde{O}(n)$ running time with probability tending to one as $n\rightarrow\infty$. As far as we know, this is the first algorithm with nearlylinear running time that achieves exact recovery at the informationtheoretical limit. We also present numerical results of the proposed algorithm to support and complement our theoretical development.
Author Information
Peng Wang (The Chinese University of Hong Kong)
Zirui Zhou (Huawei Technologies Canada)
Anthony ManCho So (The Chinese University of Hong Kong)
More from the Same Authors

2021 Poster: Optimal NonConvex Exact Recovery in Stochastic Block Model via Projected Power Method »
Peng Wang · Huikang Liu · Zirui Zhou · Anthony ManCho So 
2021 Spotlight: Optimal NonConvex Exact Recovery in Stochastic Block Model via Projected Power Method »
Peng Wang · Huikang Liu · Zirui Zhou · Anthony ManCho So