Community detection in the sparse hypergraph stochastic block model
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionStochastic Block ModelSimilar Papers 제목 키워드 기반
Sparse random hypergraphs: Non-backtracking spectra and community detection
We consider the community detection problem in a sparse $q$-uniform hypergraph $G$, assuming that $G$ is generated according to the Hypergraph Stochastic Block Model (HSBM). We prove that a spectral method based on the n…
Community DetectionDimensionality ReductionStochastic Block ModelInformation Theoretic Limits of Exact Recovery in Sub-hypergraph Models for Community Detection
In this paper, we study the information theoretic bounds for exact recovery in sub-hypergraph models for community detection. We define a general model called the $m-$uniform sub-hypergraph stochastic block model ($m-$Sh…
Community DetectionStochastic Block ModelPartial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
We consider the community detection problem in sparse random hypergraphs under the non-uniform hypergraph stochastic block model (HSBM), a general model of random networks with community structure and higher-order intera…
Community DetectionStochastic Block ModelInference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models
Hypergraphs represent complex systems involving interactions among more than two entities and allow the investigation of higher-order structure and dynamics in complex systems. Node attribute data, which often accompanie…
AttributeDimensionality ReductionStochastic Block ModelStochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
We study the problem of community detection in a random hypergraph model which we call the stochastic block model for $k$-uniform hypergraphs ($k$-SBM). We investigate the exact recovery problem in $k$-SBM and show that …
Community DetectionStochastic Block Model