Community detection in the sparse hypergraph stochastic block model
This solves a theoretical problem for researchers in network science and machine learning, but it is incremental as it generalizes an existing method from graphs to hypergraphs.
The paper tackles the community detection problem in sparse random hypergraphs by proving the positive part of a conjecture about a sharp threshold for detectability, showing that above this threshold, a spectral algorithm can asymptotically almost surely construct a partition correlated with the true one.
We consider the community detection problem in sparse random hypergraphs. Angelini et al. (2015) conjectured the existence of a sharp threshold on model parameters for community detection in sparse hypergraphs generated by a hypergraph stochastic block model. We solve the positive part of the conjecture for the case of two blocks: above the threshold, there is a spectral algorithm which asymptotically almost surely constructs a partition of the hypergraph correlated with the true partition. Our method is a generalization to random hypergraphs of the method developed by Massoulié (2014) for sparse random graphs.