Combinatorics Seminar 2018

Speaker: Yizhe Zhu (朱亦哲), University of Washington

Date: Tue, Dec 11, 2018

Time: 16:00 - 17:00

Venue: Middle Meeting Room

Title: Community detection for sparse random hypergraphs


The stochastic block model (SBM) is a generative model for random graphs, which has been one of the most fruitful research topics in community detection and clustering. A phase transition behavior for detection was conjecured by Decelle el al. (2011) at the Kesten-Stigum threshold, and was confirmed by Mossel et al. (2012,2013) and Massoulié (2014). Angelini et al. (2015) conjectured the existence of a similar sharp threshold behavior for community detection in random hypergraphs. We solved the positive part of the conjecture: the detection is possible above the threshold, and there is a spectral algorithm which constructs a correlated partition with high probability. We introduced a modified adjacency matrix which counts self-avoiding walks on hypergraphs, whose leading eigenvectors give us a reconstruction of the community structure. In the course of proving our main result, we constructed a coupling between the local neighborhood of random hypergraphs and multitype Poisson Galton-Watson hypertrees, and obtained a weak Ramanujan property for sparse random hypergraphs. This is joint work with Soumik Pal.

Slides: View slides