BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Partitioning Well-Clustered Graphs: Spectral Clustering Works! - H
 e Sun (University of Bristol)
DTSTART:20160712T103000Z
DTEND:20160712T110000Z
UID:TALK66714@talks.cam.ac.uk
CONTACT:INI IT
DESCRIPTION:We study variants of the widely used&nbsp\;<i>spectral cluster
 ing</i>&nbsp\;that&nbsp\;partitions a graph into k clusters by (1) embeddi
 ng the vertices of a graph into a low-dimensional space using the bottom e
 igenvectors of the Laplacian matrix\, and (2) grouping the embedded points
  into k clusters via k-means algorithms. We show that\, for a wide class o
 f &nbsp\;graphs\, spectral clustering gives a good approximation of the op
 timal clustering. While this approach was proposed in the early 1990s and 
 has comprehensive applications\, prior to our work &nbsp\;similar results 
 were known only for graphs generated from stochastic models.<br><br>We als
 o give a nearly-linear time algorithm for partitioning well-clustered grap
 hs based on &nbsp\;computing a matrix exponential andapproximate nearest n
 eighbor data structures.<br><span><br>Based on joint work with Richard Pen
 g (Georgia Institute of Technology)\, and Luca Zanetti (University of Bris
 tol).<br><br>Reference:&nbsp\;</span><a href="http://arxiv.org/abs/1411.20
 21" target="_blank" rel="nofollow">http://arxiv.org/abs/1411.2021</a><br>
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR