Community detection in complex networks is one of the fundamental problems in unsupervised learning, with applications from recommender systems to gene classification. In order to design state-of-the-art algorithms for community detection, as well as to predict and offer guarantees for their real-world performance, one often employs stochastic network models. The Hypergraph Stochastic Block Model (HSBM) is a set of basic models that have a lot of built-in flexibility and whose parameters can be adapted to suit various real-life networks (from social to biological and neural). One crucial issue in the study of these models is represented by the “threshold” relationships among the defining parameters: these are sets of constraints (inequalities) which characterize the difficulty of the recovery problem and describe the best possible type of algorithmic performance on a network subject to these constraints. We will provide an overview of the problem, regimes of recovery, and survey literature, and then focus on partial, almost exact, and exact recovery for variants of the HSBM.

This represents joint work with Haixiao Wang and Yizhe Zhu.