Stochastic 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 a sharp phase transition occurs around a threshold: below the threshold it is impossible to recover the communities with non-vanishing probability, yet above the threshold there is an estimator which recovers the communities almost asymptotically surely. We also consider a simple, efficient algorithm for the exact recovery problem which is based on a semidefinite relaxation technique.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionStochastic Block ModelSimilar Papers 제목 키워드 기반
Community Detection with a Subsampled Semidefinite Program
Semidefinite programming is an important tool to tackle several problems in data science and signal processing, including clustering and community detection. However, semidefinite programs are often slow in practice, so …
ClusteringCommunity DetectionStochastic Block ModelA semidefinite program for unbalanced multisection in the stochastic block model
We propose a semidefinite programming (SDP) algorithm for community detection in the stochastic block model, a popular model for networks with latent community structure. We prove that our algorithm achieves exact recove…
Community DetectionStochastic Block ModelExploiting Tradeoffs for Exact Recovery in Heterogeneous Stochastic Block Models
The Stochastic Block Model (SBM) is a widely used random graph model for networks with communities. Despite the recent burst of interest in community detection under the SBM from statistical and computational points of v…
Community DetectionStochastic Block ModelStatistical Limits of Convex Relaxations
Many high dimensional sparse learning problems are formulated as nonconvex optimization. A popular approach to solve these nonconvex optimization problems is through convex relaxations such as linear and semidefinite pro…
Sparse LearningStochastic Block ModelCommunity 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 …
Community DetectionStochastic Block Model