[SciPy-User] Graph connect components and sparse matrices

[Gael Varoquaux]

On Wed, Nov 18, 2009 at 09:03:18AM -0500, Zachary Pincus wrote:
>  From this useful tutorial on spectral clustering:
> http://www.kyb.tuebingen.mpg.de/bs/people/ule/publications/publication_downloads/Luxburg07_tutorial.pdf

> > Thus, the matrix L has as many eigenvalues 0 as there are connected
> > components, and the corresponding eigenvectors are the indicator
> > vectors of the connected components.

> (where L is the graph laplacian).

I read this tutorial (a very good one, by the way). But I am too dumb to
figure out from the above assertion how to retrieve the connect
components. Let me explain my problem on an example. Suppose that we have
the trivial graph. Its adjacency matrix is the identity, the
corresponding laplacian is null. An EVD of these matrices will result in
an abitrary orthonormal basis of my vertex space. How do I figure out the
connect components from that?

The problem arises also on non trivial graphs, by the way. The problem is
that doing an EVD of the transition of laplace matrix only gives a
subspace of the kernel of the laplace matrix. I could probably do a
sparse matrix factorization on that, but I see complexity and cost coming
in, and I am trying to avoid that.

Thanks for your answer,

Gaël