11:00 am Wednesday, April 17, 2013
Complex Networks Seminar : Improved graph clustering by Sujay Sanghavi (UT Austin, ECE dept) in RLM 12.166
Graph clustering is the following problem (in words): given a sparse graph, partition the nodes into clusters so that the edge density within a cluster is higher than the density across clusters. It is a widely studied problem, and represents a fundamental step in the pre-processing of large networks for finer-scale analysis. A classical, and natural, statistical setting to formalize this question is the stochastic block model; first a partition is chosen for the nodes, and then a graph is generated at random, with different edge probabilities within and across partitions. The problem now becomes: given just the graph, find the partition. The hardness of the problem is governed by the edge density - both overall, and the differential - and the size of the smallest partition. In this talk we present a new algorithm for this classical problem; and corresponding analytical results which establish that it outperforms the existing literature by polynomial factors. Our algorithm is spectral, but needs an asymmetric low-rank approximation that necessitates the use of convex optimization (as opposed to SVD)
Submitted by