[SciPy-User] Graph connect components and sparse matrices

[Zachary Pincus]

>> 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...