Finding connect components

[Gael Varoquaux]

Hi,

I have been playing with graphs outside of networkX, represented as
symetric sparse matrices.

I want to enumerate the connect components of my graph. If I am not
right, I can use scipy.sparse.arpack.eigen_symmetric to find out the
largest eigen vectors of the graph, use the sign of this eigen vector if
the eigen value is greater than 1 to split the graph, and iter on the sub
graphs as long as the largest eigen value is greater than one.

I happen to need the largest eigen value of each connect components (I am
doing diffusion maps), so I am going to do linear algebra anyhow. The
arpack documentation claims that the computation cost scales with the
order of the matrix
(http://www.caam.rice.edu/software/ARPACK/UG/node56.html). I am
wondering, is there any reason to detect connect doing graph traversal?
What is the computational cost of the algorithm used in networkx (~ the
order of the graph, I suppose)?

These questions are quite academic, as I have small graphs, but I like to
learn.

Thanks,

Ga�l

[Aric Hagberg]

The connected components algorithms in NetworkX use shortest path (BFS
in this case) and are linear algorithms - O(V+E).

I'm not familiar with methods to find or count the components using
the adjacency spectrum. But if you just want to count the number of
components - that is equal to the number of zero eigenvalues of the
graph Laplacian.

Aric

[alex]

Aric Hagberg wrote:
> [...]

> I'm not familiar with methods to find or count the components using
> the adjacency spectrum.

> [...]

The paper "the perturbed laplacian matrix of a graph" by Bapat et al.
unifies some theorems about laplacians and adjacency matrices, and I
think this includes an algebraic connectivity analog for the adjacency
matrix. So I would be surprised if the laplacian spectrum and the
adjacency spectrum don't agree about the connectivity of the graph.

Alex