Recovering nonuniform planted partitions via iterated projection

DOI10.1016/j.laa.2018.03.009zbMath1416.05256arXiv1708.06783OpenAlexW2963122773WikidataQ130148341 ScholiaQ130148341MaRDI QIDQ2002551

Sam Cole

Publication date: 12 July 2019

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

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

zbMATH Keywords

random graphsstochastic block modelgraph clusteringrandom symmetric matricesplanted cliqueplanted partition

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Clustering in the social and behavioral sciences (91C20) Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random matrices (algebraic aspects) (15B52) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Guaranteed clustering and biclustering via semidefinite programming
• Eigenvalue perturbation theory of classes of structured matrices under generic structured rank one perturbations
• The eigenvalues of random symmetric matrices
• Expected complexity of graph partitioning problems
• A simple spectral algorithm for recovering planted partitions
• Multipodal structure and phase transitions in large constrained graphs
• Eigenvalues of rank-one updated matrices with some applications
• An introduction to large deviations for random graphs
• Improved Graph Clustering
• Graph Partitioning via Adaptive Spectral Techniques
• Average Case Complete Problems
• Large Cliques Elude the Metropolis Process
• A Stable and Efficient Algorithm for the Rank-One Modification of the Symmetric Eigenproblem
• The phases of large networks with edge and triangle constraints
• A Simple SVD Algorithm for Finding Hidden Partitions
• Finding and certifying a large hidden clique in a semirandom graph
• Computational Complexity
• Fundamentals of Computation Theory
• Statistical algorithms and a lower bound for detecting planted cliques
• Simultaneous similarity of matrices

This page was built for publication: Recovering nonuniform planted partitions via iterated projection