# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Partitioning Well-clustered Graphs with k-Means and Heat Kernel

##### Locator

There are no locators available

##### Fulltext (public)

arXiv:1411.2021.pdf

(Preprint), 349KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Peng, R., Sun, H., & Zanetti, L. (2014). Partitioning Well-clustered Graphs with k-Means and Heat Kernel. Retrieved from http://arxiv.org/abs/1411.2021.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0024-42E4-4

##### Abstract

We study a suitable class of well-clustered graphs that admit good k-way
partitions and present the first almost-linear time algorithm for with
almost-optimal approximation guarantees partitioning such graphs. A good k-way
partition is a partition of the vertices of a graph into disjoint clusters
(subsets) $\{S_i\}_{i=1}^k$, such that each cluster is better connected on the
inside than towards the outside. This problem is a key building block in
algorithm design, and has wide applications in community detection and network
analysis.
Key to our result is a theorem on the multi-cut and eigenvector structure of
the graph Laplacians of these well-clustered graphs. Based on this theorem, we
give the first rigorous guarantees on the approximation ratios of the widely
used k-means clustering algorithms. We also give an almost-linear time
algorithm based on heat kernel embeddings and approximate nearest neighbor data
structures.