[SciPy-User] Graph connect components and sparse matrices
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,
More information about the SciPy-User