A simple spectral algorithm for recovering planted partitions

DOI10.1515/spma-2017-0013zbMath1392.05098arXiv1503.00423OpenAlexW2963047374MaRDI QIDQ1678989

Lev Reyzin, Sam Cole, Shmuel Friedland

Publication date: 8 November 2017

Published in: Special Matrices (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Eigenvector Computation and Community Detection in Asynchronous Gossip Models, Recovering nonuniform planted partitions via iterated projection, Exact recovery in the hypergraph stochastic block model: a spectral algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Guaranteed clustering and biclustering via semidefinite programming
• Nuclear norm minimization for the planted clique and biclique problems
• Matrix multiplication via arithmetic progressions
• The eigenvalues of random symmetric matrices
• Expected complexity of graph partitioning problems
• On the concentration of eigenvalues of random symmetric matrices
• Improved Graph Clustering
• Powers of tensors and fast matrix multiplication
• Graph Partitioning via Adaptive Spectral Techniques
• Large Cliques Elude the Metropolis Process
• Cliques in random graphs
• A Simple SVD Algorithm for Finding Hidden Partitions
• Finding and certifying a large hidden clique in a semirandom graph
• A fast and efficient algorithm for low-rank approximation of a matrix
• Subspace Iteration Randomization and Singular Value Problems
• Finding Hidden Cliques in Linear Time with High Probability
• Fundamentals of Computation Theory
• Statistical algorithms and a lower bound for detecting planted cliques
• Spectral norm of random matrices