[SciPy-User] Graph connect components and sparse matrices

Gael Varoquaux gael.varoquaux@normalesup....
Wed Nov 18 10:22:51 CST 2009


On Wed, Nov 18, 2009 at 09:55:17AM -0500, Zachary Pincus wrote:
> >> 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.

> > My linear algebra is only tenuous at best, so I don't exactly see why
> > this is a problem. As far as I understand, to find the connected
> > components, first you find the eigenvectors of the laplacian that have
> > an eigenvalue of zero. Then for each node in the graph i, there will
> > be exactly one eigenvector with a non-zero value at position i. The
> > index of this eigenvector is the index of the connected component that
> > i belongs to.

> Wait... you're saying that the eigenvectors will only span a subspace  
> of the kernel, so that there must be at least some position i where  
> there is a zero value in each eigenvector? 

Yes, that's it. The eigenvectors are defined only at a rotation.

> If this is correct then I  see the problem; hopefully someone who
> actually knows what they're  talking about can help me out here...

So do I :)

Thanks for your thoughts,

Gaël


More information about the SciPy-User mailing list