[SciPy-User] Graph connect components and sparse matrices

[Zachary Pincus]

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

Good question! On the other hand, IIRC the eigenvectors of the zero  
matrix are usually defined to be the unit basis vectors, so that  
solves this particular edge case.

Note that at least the non-sparse routines in numpy do this:

  numpy.linalg.eig(numpy.zeros((5,5)))

(array([ 0.,  0.,  0.,  0.,  0.]),
  array([[ 1.,  0.,  0.,  0.,  0.],
        [ 0.,  1.,  0.,  0.,  0.],
        [ 0.,  0.,  1.,  0.,  0.],
        [ 0.,  0.,  0.,  1.,  0.],
        [ 0.,  0.,  0.,  0.,  1.]]))

So there we have exactly what you want in the trivial case.

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

Is that right? Again, my linear algebra is rusty.

Zach