Community Detection in Censored Hypergraph

DOI10.5705/SS.202021.0392MaRDI QIDQ6185140zbMATH OpenFDO

Authors

Publication date 29 January 2024

Published in STATISTICA SINICA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.03179

zbMATH Keywords

censored hypergraphcommunity detectionexact recoveryinformation-theoretic threshold

Mathematics Subject Classification ID

Statistics (62-XX)

Abstract: 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.

Cites work

• A proof of the block model threshold conjecture
• A survey of statistical network models
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Community detection and stochastic block models: recent developments
• Community detection in degree-corrected block models
• Community detection with dependent connectivity
• Community Recovery in Hypergraphs
• Consistency of spectral clustering in stochastic block models
• Consistency of spectral hypergraph partitioning under planted partition model
• Exact Recovery in the Stochastic Block Model
• Fast community detection by SCORE
• Neighborhood hypergraph based classification algorithm for incomplete information system
• Reconstruction and estimation in the planted partition model
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
• Sharp detection boundaries on testing dense subhypergraph

This page was built for publication: Community Detection in Censored Hypergraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6185140)