Graph Laplacian : very small values instead of zeros
1 次查看(过去 30 天)
显示 更早的评论
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 个评论
回答(1 个)
Bruno Luong
2020-9-5
编辑:Bruno Luong
2020-9-5
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 .
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!