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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Leveraging Predictive Equivalence in Decision Trees
Cross-Domain Conditional Diffusion Models for Time Series Imputation
Learning to Collaborate Over Graphs: A Selective Federated Multi-Task Learning Approach
RADAR: Benchmarking Language Models on Imperfect Tabular Data
IMTS is Worth Time $\times$ Channel Patches: Visual Masked Autoencoders for Irregular Multivariate Time Series Prediction
Integrative Analysis and Imputation of Multiple Data Streams via Deep Gaussian Processes
토론
이 논문과 연결된 포럼 글이 아직 없습니다.