Community detection in the sparse hypergraph stochastic block model
arXiv:1904.05981 · doi:10.1002/rsa.21006
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.
arXiv comment44 pages, 5 figures
References in corpus (8)
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
- Belief propagation, robust reconstruction and optimal recovery of block models
- Spectral Detection on Sparse Hypergraphs
- 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