University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Partitioning Well-Clustered Graphs: Spectral Clustering Works!

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Download to your calendar using vCal

If you have a question about this talk, please contact INI IT .

SNAW01 - Graph limits and statistics

We study variants of the widely used spectral clustering that partitions a graph into k clusters by (1) embedding the vertices of a graph into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix, and (2) grouping the embedded points into k clusters via k-means algorithms. We show that, for a wide class of  graphs, spectral clustering gives a good approximation of the optimal clustering. While this approach was proposed in the early 1990s and has comprehensive applications, prior to our work  similar results were known only for graphs generated from stochastic models.

We also give a nearly-linear time algorithm for partitioning well-clustered graphs based on  computing a matrix exponential andapproximate nearest neighbor data structures.

Based on joint work with Richard Peng (Georgia Institute of Technology), and Luca Zanetti (University of Bristol).

Reference:  http://arxiv.org/abs/1411.2021

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

causes of hair loss teenage males Lecture Theatre 1 Cambridge Judge Business School, University of Cambridge, Trumpington Street, Cambridge CB2 1AG, UK CPES

Other talks

Title and abstract tba Scattering Plenty: the people who made the modern countryside Title and abstract tba Group Work Organiser's Welcome Title to be confirmed
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity