Graph Laplacian : very small values instead of zeros

Hello everyone,

Trying to write a function that outputs whether a graph is connected, amongst other things (directed/undirected and simple/with loops).

Using the eigenvalue spectrum to figure out if the graph is connected, as conncomp won't work if it is directed.

However, Matlab will output extremely small values ~ e-15 where zeros are meant to be (had a graph with 20 components and got 20 such values instead of 20 zeros, as per 'theory').

Currently 'bypassing' this by rounding the spectrum, to 10 significant digits.

However, this doesn't feel too 'safe'. How low can an eigenvalue go while the matrix is still connected (1 component only)?

Truly not a maths expert by the way.

Thanks a lot!

Answer 1

[Bruno Luong]

Roughly the smallest non-zero eigenvalue of the laplacian has lower bound of

2*(1-cos(pi/N))

where N is the longest path of your graph.

For "large" N, it's simpler to approximate the bound by

(pi/N)^2.

So you can always take a safe threshold of N get not larger than 10^7, which is a lot.

As alternative you can create a graph from you digraph and use conncomp .

[Eleanna Kritikaki]

Oh thanks so much. That's really helpful