[SciPy-User] Graph connect components and sparse matrices
Zachary Pincus
zachary.pincus@yale....
Wed Nov 18 08:55:17 CST 2009
>> 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? If this is correct then I
see the problem; hopefully someone who actually knows what they're
talking about can help me out here...
More information about the SciPy-User
mailing list