Partitioning Well-Clustered Graphs: Spectral Clustering Works!

DOI10.1137/15M1047209zbMath1370.05204arXiv1411.2021MaRDI QIDQ5737808

Luca Zanetti, He Sun, Richard Peng

Publication date: 30 May 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

heat kernelgraph partitioningspectral clustering\(k\)-means

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (15)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model ⋮ Unnamed Item ⋮ Find Your Place: Simple Distributed Algorithms for Community Detection ⋮ Communication-efficient distributed graph clustering and sparsification under duplication models ⋮ Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm ⋮ Unnamed Item ⋮ Step-by-step community detection in volume-regular graphs ⋮ Approximating Spectral Clustering via Sampling: A Review ⋮ Good (K-means) clusterings are unique (up to small perturbations) ⋮ Bipartite communities via spectral partitioning ⋮ Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem ⋮ Convex programming based spectral clustering ⋮ Rate-optimal cluster-randomized designs for spatial interference ⋮ Distributed detection of clusters of arbitrary size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spectral clustering and the high-dimensional stochastic blockmodel
• Center-based clustering under perturbation stability
• Sparsest cuts and bottlenecks in graphs
• Sorting noisy data with partial information
• Spectral Sparsification of Graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Subexponential Algorithms for Unique Games and Related Problems
• On clusterings
• A Simple SVD Algorithm for Finding Hidden Partitions
• A Note On Spectral Clustering
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• Partitioning into Expanders
• A Local Graph Partitioning Algorithm Using Heat Kernel Pagerank
• The effectiveness of lloyd-type methods for the k-means problem
• Multi-way spectral partitioning and higher-order cheeger inequalities
• Many sparse cuts via higher eigenvalues
• Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
• Improved Cheeger's inequality
• The Rotation of Eigenvectors by a Perturbation. III
• Expander flows, geometric embeddings and graph partitioning
• Graph Sparsification by Effective Resistances

This page was built for publication: Partitioning Well-Clustered Graphs: Spectral Clustering Works!