The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Clustering Sparse Graphs

Sanghavi, S (University of Texas at Austin)
Wednesday 14 August 2013, 10:00-10:45

Seminar Room 1, Newton Institute


Graph clustering involves the task of partitioning nodes, so that the edge density is higher within partitions as opposed to across partitions. A natural problem, it represents a first step in a wide array of applications in network analysis, community detection, recommendation systems etc.

A classic and popular statistical setting for evaluating between different solutions to this problem is the stochastic block model, also referred to as the planted partition model. In this talk, we present a new algorithm for this problem, which improves by polynomial factors over the performance of all previous known algorithms. It is based on convex optimization, and draws a connection between this problem and a different field: high-dimensional statistical inference.


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧