You are here

Community detection in sparse random hypergraphs

Yizhe Zhu, UW Mathematics
Monday, May 20, 2019 - 2:30pm to 3:30pm
MEB 238

The stochastic block model (SBM) is a generative model for random graphs with a community structure, which has been one of the most fruitful research topics in community detection and clustering. A phase transition behavior for detection was conjectured by Decelle el al. (2011), and was confirmed by Mossel et al. (2012, 2013) and Massoulié (2013). We consider the community detection problem in random hypergraphs. Angelini et al. (2015) conjectured a phase transition for community detection in sparse hypergraphs generated by a hypergraph stochastic block model (HSBM). We confirmed the positive part of the phase transition for the 2-block case by a generalization of the method developed in Massoulié (2013) for sparse random graphs. 

We introduced a matrix which counts self-avoiding walks on hypergraphs, whose leading eigenvectors give us a correlated reconstruction of the community structure. In the course of proving our main result, we developed a moment method for sparse hypergraphs and constructed a coupling between the local neighborhood of HSBMs and multitype Poisson Galton-Watson hypertrees. This is joint work with Soumik Pal.

Event Type: 
Event Subcalendar: