A Simple SVD Algorithm for Finding Hidden Partitions
From MaRDI portal
Abstract: Finding a hidden partition in a random environment is a general and important problem, which contains as subproblems many famous questions, such as finding a hidden clique, finding a hidden coloring, finding a hidden bipartition etc. In this paper, we provide a simple SVD algorithm for this purpose, answering a question of McSherry. This algorithm is very easy to implement and works for sparse graphs with optimal density.
Recommendations
- A simple spectral algorithm for recovering planted partitions
- An SVD-like matrix decomposition and its applications
- A Divide-and-Conquer Algorithm for the Bidiagonal SVD
- scientific article; zbMATH DE number 641554
- Partial singular value decomposition algorithm
- A Numerical Method for Computing an SVD-like Decomposition
- The vectorization of the partition problem
- On Kogbetliantz's SVD algorithm in the presence of clusters
- An algorithm for partitioning a set into simple parts
- An algorithm for nontransitive partitions
Cites work
- A new look at independence
- A Spectral Technique for Coloring Random 3-Colorable Graphs
- Algorithms for graph partitioning on the planted partition model
- Almost all k-colorable graphs are easy to color
- Coloring Random and Semi-Random k-Colorable Graphs
- Finding and certifying a large hidden clique in a semirandom graph
- Finding hidden cliques in linear time
- Finding hidden cliques in linear time with high probability
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Graph partitioning via adaptive spectral techniques
- scientific article; zbMATH DE number 5691097 (Why is no real title available?)
- scientific article; zbMATH DE number 3608053 (Why is no real title available?)
- scientific article; zbMATH DE number 1246230 (Why is no real title available?)
- scientific article; zbMATH DE number 1380608 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Perturbation bounds in connection with singular value decomposition
- Random weighted projections, random quadratic forms and random eigenvectors
- Spectral algorithms
- Spectral analysis of data
- Spectral norm of random matrices
- Spectral techniques applied to sparse random graphs
- The eigenvalues of random symmetric matrices
- The Rotation of Eigenvectors by a Perturbation. III
Cited in
(26)- A simple spectral algorithm for recovering planted partitions
- Recovering the structure of random linear graphs
- Layout of random circulant graphs
- Recovering nonuniform planted partitions via iterated projection
- Convex relaxation methods for community detection
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- Consistent nonparametric estimation for heavy-tailed sparse graphs
- Optimality of spectral clustering in the Gaussian mixture model
- A multiscale environment for learning by diffusion
- Rate optimal Chernoff bound and application to community detection in the stochastic block models
- Entrywise eigenvector analysis of random matrices with low expected rank
- scientific article; zbMATH DE number 7255037 (Why is no real title available?)
- Optimal bipartite network clustering
- Strong consistency, graph Laplacians, and the stochastic block model
- Eigenvector Computation and Community Detection in Asynchronous Gossip Models
- Graph powering and spectral robustness
- Model-free nonconvex matrix completion: local minima analysis and applications in memory-efficient kernel PCA
- Partitioning well-clustered graphs: spectral clustering works!
- Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
- A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
- Subexponential-time algorithms for sparse PCA
- Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model
- Clustering large graphs via the singular value decomposition
- Analysis of singular subspaces under random perturbations
- Spectral clustering with likelihood refinement for high-dimensional latent class recovery
- Estimating the number of communities by spectral methods
This page was built for publication: A Simple SVD Algorithm for Finding Hidden Partitions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601058)
