Community detection in the sparse hypergraph stochastic block model

2019/04/30 by Soumik Pal, Yizhe Zhu
Computer Science · Mathematics · Physics and Astronomy · #Block (permutation group theory) #Complex Network Analysis Techniques #Conjecture #Generalization #Hypergraph #Limits and Structures in Graph Theory #Opinion Dynamics and Social Influence #Partition (number theory) #Stochastic block model #cs.LG #cs.SI #math.CO #math.PR #stat.ML

paper · pdf · doi:10.1002/rsa.21006

published as Random Struct Alg. 2021, 59(3), 407-463 · 44 pages, 5 figures

openalex created_date 2019/04/25 · openalex publication_date 2021/03/14 · arxiv created 2021/07/08 · arxiv updated 2021/08/05 · openalex updated_date 2026/08/06

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.

Citations

• Reconstruction and estimation in the planted partition model
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption in clustering sparse networks
• Most Tensor Problems Are NP-Hard