Community detection in the sparse hypergraph stochastic block model. Issue 3 (14th March 2021)

• Record Type: Journal Article
• Authors: Pal, Soumik; Zhu, Yizhe
• Is Part Of: Random structures & algorithms. Volume 59:Issue 3(2021)
• Page Start: 407
• Page End: 463
• Publication Date: 2021-03-14
• Subjects: community detection -- random tensor -- self‐avoiding walk -- sparse hypergraph -- stochastic block model; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21006
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We consider the community detection problem in sparse random hypergraphs. Angelini et al. in [6] 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.