[SciPy-User] Graph connect components and sparse matrices

[Zachary Pincus]

Hi Gaël,

> Any idea how I could squeeze the information out of the sparse linear
> algebra that we carry around with scipy? I thought about using  
> arpack to
> get the largest eigen vectors of the transition matrix, but that was a
> stupid idea, as (AFAIK) it will not partition my graph in connect
> components, but only tell me how many connect components I have.

 From this useful tutorial on spectral clustering:
http://www.kyb.tuebingen.mpg.de/bs/people/ule/publications/publication_downloads/Luxburg07_tutorial.pdf

> Thus, the matrix L has as many eigenvalues 0 as there are connected  
> components, and
> the corresponding eigenvectors are the indicator vectors of the  
> connected components.

(where L is the graph laplacian).

Zach



On Nov 18, 2009, at 8:46 AM, Gael Varoquaux wrote:

> Hi there,
>
> I would like to list the connect components of a graph (or a sparse
> matrix, same thing). I know of course of the bread-first traversal, as
> implemented eg in networkX, to find the connect components. However, I
> have a feeling that sparse linear algebra must be performing such
> searches, to decompose sparse matrices in blocks. I'd love to piggy  
> back
> on such implementations, rather than code and maintain a C or cython
> version of breadth-first graph traversal.
>
> Any idea how I could squeeze the information out of the sparse linear
> algebra that we carry around with scipy? I thought about using  
> arpack to
> get the largest eigen vectors of the transition matrix, but that was a
> stupid idea, as (AFAIK) it will not partition my graph in connect
> components, but only tell me how many connect components I have.
>
> Gaël
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user