| Full text | Click to download. |
| Citation | in Proceedings of the 2006 European Symposium
on Algorithms.
|
| Authors | Anirban Dasgupta
John Hopcroft Ravi Kannan Pradipta Mitra |
In this paper, we analyze the second eigenvector technique of spectral partitioning on the planted partition random graph model, by constructing a recursive algorithm using the second eigenvectors in order to learn the planted partitions. The correctness of our algorithm is not based on the ratio-cut interpretation of the second eigenvector, but exploits instead the stability of the eigenvector subspace. As a result, we get an improved cluster separation bound in terms of dependence on the maximum variance. We also extend our results for a clustering problem in the case of sparse graphs.