Community detection with the Bethe-Hessian
Assistant Professor of Electrical and Computer Engineering
This research seminar investigates the application of the Bethe-Hessian matrix for community detection in sparse networks. It presents a rigorous analysis of the Bethe-Hessian spectral method within the stochastic block model, contrasting it with the non-backtracking operator.
Yizhe Zhu (USC)
Beyond Graph Laplacians
The Bethe-Hessian matrix, introduced by Saade, Krzakala, and Zdeborová (2014), is a Hermitian matrix designed for applying spectral clustering algorithms to sparse networks. Rather than employing a non-symmetric and high-dimensional non-backtracking operator, a spectral method based on the Bethe-Hessian matrix is conjectured to also reach the Kesten-Stigum detection threshold in the sparse stochastic block model (SBM). We provide a rigorous analysis of the Bethe-Hessian spectral method in the SBM under both the bounded expected degree and the growing degree regimes.