Graph Laplacian : very small values instead of zeros
1 vue (au cours des 30 derniers jours)
Afficher commentaires plus anciens
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!
0 commentaires
Réponses (1)
Bruno Luong
le 5 Sep 2020
Modifié(e) : Bruno Luong
le 5 Sep 2020
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 .
Voir également
Catégories
En savoir plus sur Graph and Network Algorithms dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!