Community detection in the sparse hypergraph stochastic block model

Abstract

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.

44 pages, 5 figures

References in corpus (3)

• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
• Graph powering and spectral robustness
• Load Balancing in Hypergraphs

Cited by in corpus (6)

• A framework to generate hypergraphs with community structure
• Sparse random tensors: Concentration, regularization and applications
• Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
• Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model
• Multilayer hypergraph clustering using the aggregate similarity matrix
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model