Exact recovery in the hypergraph stochastic block model: a spectral algorithm

DOI10.1016/j.laa.2020.01.039zbMath1436.05094arXiv1811.06931OpenAlexW2900800369MaRDI QIDQ2310389

Yizhe Zhu, Sam Cole

Publication date: 6 April 2020

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

spectral algorithmcommunity detectionstochastic block modelrandom hypergraph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Independent sets in semi-random hypergraphs ⋮ Multilayer hypergraph clustering using the aggregate similarity matrix ⋮ Community detection in the sparse hypergraph stochastic block model ⋮ Sparse random tensors: concentration, regularization and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tensor Decompositions and Applications
• Consistency thresholds for the planted bisection model
• Minimax rates of community detection in stochastic block models
• A reductive approach to hypergraph clustering: an application to image segmentation
• Guaranteed clustering and biclustering via semidefinite programming
• Reconstruction and estimation in the planted partition model
• Consistency of spectral hypergraph partitioning under planted partition model
• Expected complexity of graph partitioning problems
• A simple spectral algorithm for recovering planted partitions
• A proof of the block model threshold conjecture
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Spectra of hypergraphs and applications
• Recovering nonuniform planted partitions via iterated projection
• Entrywise eigenvector analysis of random matrices with low expected rank
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Exact Recovery in the Stochastic Block Model
• Improved Graph Clustering
• Loose laplacian spectra of random hypergraphs
• Handbook of Approximation Algorithms and Metaheuristics
• Average Case Complete Problems
• Large Cliques Elude the Metropolis Process
• Community Detection and Stochastic Block Models
• Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
• High-Dimensional Probability
• Finding and certifying a large hidden clique in a semirandom graph
• Community Recovery in Hypergraphs
• On the Minimax Misclassification Ratio of Hypergraph Community Detection
• Subspace Iteration Randomization and Singular Value Problems
• Community detection thresholds and the weak Ramanujan property
• Graph-Based Representations in Pattern Recognition
• Computational Complexity

This page was built for publication: Exact recovery in the hypergraph stochastic block model: a spectral algorithm