CS 789 THEORY SEMINAR [home]

Speaker:    Anirban Dasgupta
Affiliation:  Cornell University
Date:          October 4, 2004
Title:          Spectral analysis for random graphs with skewed degree distributions
 

Abstract: 

Spectral analysis, performed using the eigenvectors of the data matrix, is a very effective heuristic for graph clustering and for data mining in general. For proving the correctness of spectral analysis, researchers have come up with different frameworks of clustering in graph models.
In this talk, I will describe a particular graph model, based on the Erdos random graph, under which we can show the correctness of a spectral algorithm. In particular we extend the work of McSherry and show that a normalized version of spectral analysis can be proven to work well even for graph models with skewed degree distributions.

To appear in FOCS 2004. Joint work with John Hopcroft and Frank McSherry.