The stochastic block model has been one of the most fruitful research topics in community detection and clustering. Recently, community detection on hypergraphs has become an important topic in higher-order network analysis. We consider the detection problem in a sparse random tensor model called the hypergraph stochastic block model (HSBM). We prove that a spectral method based on the non-backtracking operator for hypergraphs works with high probability down to the generalized Kesten-Stigum detection threshold conjectured by Angelini et al (2015). We characterize the spectrum of the non-backtracking operator for sparse random hypergraphs and provide an efficient dimension reduction procedure using the Ihara-Bass formula for hypergraphs. As a result, the community detection problem can be reduced to an eigenvector problem of a non-normal matrix constructed from the adjacency matrix of the hypergraph. Based on joint work with Ludovic Stephan (EPFL).
Probability and Combinatorics
Tuesday, November 29, 2022 - 3:30pm
Yizhe Zhu
University of California, Irvine
Other Events on This Day
-
Universality classes in traveling waves modeled by stochastic reaction-diffusion equations
MathBio Seminar
4:00pm