English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

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

MPS-Authors
/persons/resource/persons45576

Sun,  He
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons136368

Zanetti,  Luca
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.