Community detection in censored hypergraph
Community detection refers to the problem of clustering the nodes of a network (either graph or hypergrah) into groups. Various algorithms are available for community detection and all these methods apply to uncensored networks. In practice, a network may has censored (or missing) values and it is shown that censored values have non-negligible effect on the structural properties of a network. In this paper, we study community detection in censored $m$-uniform hypergraph from information-theoretic point of view. We derive the information-theoretic threshold for exact recovery of the community structure. Besides, we propose a polynomial-time algorithm to exactly recover the community structure up to the threshold. The proposed algorithm consists of a spectral algorithm plus a refinement step. It is also interesting to study whether a single spectral algorithm without refinement achieves the threshold. To this end, we also explore the semi-definite relaxation algorithm and analyze its performance.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionMissing ValuesSimilar Papers 제목 키워드 기반
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 …
Community DetectionStochastic Block ModelHypergraph Artificial Benchmark for Community Detection (h-ABCD)
The Artificial Benchmark for Community Detection (ABCD) graph is a recently introduced random graph model with community structure and power-law distribution for both degrees and community sizes. The model generates grap…
Community DetectionCommunity Detection in General Hypergraph via Graph Embedding
Conventional network data has largely focused on pairwise interactions between two entities, yet multi-way interactions among multiple entities have been frequently observed in real-life hypergraph networks. In this arti…
Community DetectionGraph EmbeddingInformation 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 ModelSparse 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 Model