Jiapeng Zhang




Wednesday, November 30, 2022 - 2:00pm to 3:00pm



510R Rowland Hall

Community detection in the stochastic block model is one of the central problems of graph clustering. In this setup, spectral algorithms have been one of the most widely used frameworks for the design of clustering algorithms. However, despite the long history of study, there are still unsolved challenges. One of the main open problems is the design and analysis of ``simple'' spectral algorithms, especially when the number of communities is large. 

In this talk, I will discuss two algorithms. The first one is based on the power-iteration method. Our algorithm performs optimally (up to logarithmic factors) compared to the best known bounds in the dense graph regime by Van Vu (Combinatorics Probability and Computing, 2018). 

Then based on a connection between the powered adjacency matrix and eigenvectors, we provide a ``vanilla'' spectral algorithm for large number of communities in the balanced case. Our spectral algorithm is as simple as PCA (principal component analysis).

This talk is based on joint works with Chandra Sekhar Mukherjee. (https://arxiv.org/abs/2211.03939)