BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Partitioning Well-Clustered Graphs: Spectral Clust
ering Works! - He Sun (University of Bristol)
DTSTART;TZID=Europe/London:20160712T113000
DTEND;TZID=Europe/London:20160712T120000
UID:TALK66714AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/66714
DESCRIPTION:We study variants of the widely used \;spec
tral clustering \;that \;partitions a
graph into k clusters by (1) embedding the vertice
s of a graph into a low-dimensional space using th
e bottom eigenvectors of the Laplacian matrix\, an
d (2) grouping the embedded points into k clusters
via k-means algorithms. We show that\, for a wide
class of  \;graphs\, spectral clustering give
s a good approximation of the optimal clustering.
While this approach was proposed in the early 1990
s and has comprehensive applications\, prior to ou
r work  \;similar results were known only for
graphs generated from stochastic models.
We
also give a nearly-linear time algorithm for part
itioning well-clustered graphs based on  \;com
puting a matrix exponential andapproximate nearest
neighbor data structures.
Based on j
oint work with Richard Peng (Georgia Institute of
Technology)\, and Luca Zanetti (University of Bris
tol).
Reference: \;http://arxiv.org/abs/1411.2021
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:INI IT
END:VEVENT
END:VCALENDAR