Reconstructing Many Partitions Using Spectral Techniques

Joachim Giesen, Dieter Mitsche

Type: Book-Chapter

Publication Date: 2005-01-01

Citations: 24

DOI: https://doi.org/10.1007/11537311_38

View Publication

Locations

Lecture notes in computer science - View

Similar Works

Action	Title	Year	Authors
+	Boosting Spectral Partitioning by Sampling and Iteration	2005	Joachim Giesen Dieter Mitsche
+	An Iterative Spectral Approach to Recovering Planted Partitions	2018	Samuel Cole
+ PDF Chat	Graph Partitioning via Adaptive Spectral Techniques	2009	Amin Coja‐Oghlan
+	Graph partitioning via adaptive spectral techniques.	2006	Amin Coja‐Oghlan
+	Recovering nonuniform planted partitions via iterated projection	2018	Sam Cole
+	A Simple Spectral Algorithm for Recovering Planted Partitions	2015	Sam Cole Shmuel Friedland Lev Reyzin
+	SPECTRAL TECHNIQUES FOR PARTITIONING PLANTED RANDOM GRAPHS	2013	Yufei Zhao
+ PDF Chat	A simple spectral algorithm for recovering planted partitions	2017	Sam Cole Shmuel Friedland Lev Reyzin
+	Recovering Nonuniform Planted Partitions via Iterated Projection	2017	Sam Cole
+	An Adaptive Spectral Heuristic for Partitioning Random Graphs	2006	Amin Coja‐Oghlan
+	Partitioning Well-Clustered Graphs: Spectral Clustering Works!	2014	Richard Peng He Sun Luca Zanetti
+ PDF Chat	Partitioning Well-Clustered Graphs: Spectral Clustering Works!	2017	Richard Peng He Sun Luca Zanetti
+	Spectral partitioning of random graphs	2001	Frank McSherry
+	Spectral Algorithms Optimally Recover Planted Sub-structures	2022	Souvik Dhara Julia Gaudio Elchanan Mossel Colin Sandon
+	Finding Planted Partitions in Nearly Linear Time using Arrested Spectral Clustering	2010	Nader H. Bshouty Philip M. Long
+ PDF Chat	Reconstruction and estimation in the planted partition model	2014	Elchanan Mossel Joseph Neeman Allan Sly
+	Consistency of Spectral Algorithms for Hypergraphs under Planted Partition Model	2018	Debarghya Ghoshdastidar
+	A Practical Regularity Partitioning Algorithm and its Applications in Clustering	2012	Gábor N. Sárközy Fei Song Endre Szemerédi Shubhendu Trivedi
+	A Practical Regularity Partitioning Algorithm and its Applications in Clustering	2012	Gábor N. Sárközy Fei Song Endre Szemerédi Shubhendu Trivedi
+	Clustering Sparse Graphs	2012	Yudong Chen Sujay Sanghavi Huan Xu

Works That Cite This (17)

Action	Title	Year	Authors
+	A Simple Spectral Algorithm for Recovering Planted Partitions	2015	Sam Cole Shmuel Friedland Lev Reyzin
+	Clustering Partially Observed Graphs via Convex Optimization	2011	Yudong Chen Ali Jalali Sujay Sanghavi Huan Xu
+	Unified $\ell_{2\rightarrow\infty}$ Eigenspace Perturbation Theory for Symmetric Random Matrices	2019	Lihua Lei
+ PDF Chat	A simple spectral algorithm for recovering planted partitions	2017	Sam Cole Shmuel Friedland Lev Reyzin
+	Recovering nonuniform planted partitions via iterated projection	2018	Sam Cole
+	Spectral Partitioning of Random Graphs with Given Expected Degrees	2006	Amin Coja‐Oghlan Andreas Goerdt André Lanka
+	Clustering partially observed graphs via convex optimization	2014	Yudong Chen Ali Jalali Sujay Sanghavi Huan Xu
+	Boosting Spectral Partitioning by Sampling and Iteration	2005	Joachim Giesen Dieter Mitsche
+	Spectral Partitioning of Random Graphs with Given Expected Degrees - Detailed Version	2009	Amin Coja‐Oghlan Andreas Goerdt André Lanka
+	Sharp performance bounds for graph clustering via convex optimization	2014	Ramya Korlakai Vinayak Samet Oymak Babak Hassibi

Works Cited by This (7)

Action	Title	Year	Authors
+	Spectral partitioning of random graphs	2001	Frank McSherry
+	Algorithms for graph partitioning on the planted partition model	2001	Anne Condon Richard M. Karp
+ PDF Chat	On the concentration of eigenvalues of random symmetric matrices	2002	Noga Alon Michael Krivelevich Van H. Vu
+	Spectral partitioning works: planar graphs and finite element meshes	1996	Daniel A. Spielman Shang‐Hua Teng
+	The eigenvalues of random symmetric matrices	1981	Zoltán Füredi János Komlós
+ PDF Chat	Max Cut for Random Graphs with a Planted Partition	2004	B Bollobás Alex Scott
+ PDF Chat	Finding a large hidden clique in a random graph	1998	Noga Alon Michael Krivelevich Benny Sudakov