Community detection in the sparse hypergraph stochastic block model
From MaRDI portal
Publication:6074664
DOI10.1002/RSA.21006zbMATH Open1522.05441arXiv1904.05981MaRDI QIDQ6074664FDOQ6074664
Authors: Soumik Pal, Yizhe Zhu 
Publication date: 12 October 2023
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
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'{e} (2014) for sparse random graphs.
Full work available at URL: https://arxiv.org/abs/1904.05981
Recommendations
- A proof of the block model threshold conjecture
- Community detection thresholds and the weak Ramanujan property
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Community detection in sparse random networks
- Testing community structure for hypergraphs
Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Density (toughness, etc.) (05C42)
Cites Work
- A proof of the block model threshold conjecture
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- Spectral redemption in clustering sparse networks
- Belief propagation, robust reconstruction and optimal recovery of block models
- Community detection and stochastic block models: recent developments
- Concentration inequalities. A nonasymptotic theory of independence
- Reconstruction and estimation in the planted partition model
- Community detection thresholds and the weak Ramanujan property
- Exact Recovery in the Stochastic Block Model
- Community detection in sparse networks via Grothendieck's inequality
- Most tensor problems are NP-hard
- Broadcasting on trees and the Ising model.
- Loose Laplacian spectra of random hypergraphs
- Consistency of spectral hypergraph partitioning under planted partition model
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Proof of the achievability conjectures for the general stochastic block model
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- Load balancing in hypergraphs
- Recovery and rigidity in a regular stochastic block model
- Hypergraph with sampling for image retrieval
- Graph powering and spectral robustness
- On the Minimax Misclassification Ratio of Hypergraph Community Detection
Cited In (26)
- Oriented and degree-generated block models: generating and inferring communities with inhomogeneous degree distributions
- Graphical models based hierarchical probabilistic community discovery in large-scale social networks
- Testing community structure for hypergraphs
- Community detection in degree-corrected block models
- Characterization of expansion-related properties of modular graphs
- Community detection on Euclidean random graphs
- A Block Model for Node Popularity in Networks with Community Structure
- Learning sparse graphons and the generalized Kesten-Stigum threshold
- Multilayer hypergraph clustering using the aggregate similarity matrix
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- Optimal couplings between sparse block models
- Detection thresholds for the \(\beta\)-model on sparse graphs
- Message-passing on hypergraphs: detectability, phase transitions and higher-order information
- Two-sample test of stochastic block models via the maximum sampling entry-wise deviation
- A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
- Sharp detection boundaries on testing dense subhypergraph
- Flow-Based Community Detection in Hypergraphs
- Probabilistic Community Detection With Unknown Number of Communities
- Community detection thresholds and the weak Ramanujan property
- Sparse random hypergraphs: non-backtracking spectra and community detection
- Title not available (Why is that?)
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Community detection in sparse networks via Grothendieck's inequality
- Consistency of spectral hypergraph partitioning under planted partition model
- Finding one community in a sparse graph
- Community detection in sparse random networks
This page was built for publication: Community detection in the sparse hypergraph stochastic block model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074664)
