清空筛选条件
清空筛选条件

Graph Laplacian : very small values instead of zeros

1 次查看（过去 30 天）
Eleanna Kritikaki
编辑： Bruno Luong 2020-9-5
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!

请先登录，再回答此问题。

回答（1 个）

Bruno Luong
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!

Translated by