New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
laplacian_matrix() needs tests #1102
Comments
The calculation of the normalized Laplacian matrix is not documented for directed graphs. Consider the graph 1 -> 2. The out-degree of vertex 1, 2 is zero, one, respectively. The formula in the documentation leads to division by zero.
Note that
Weights and multi-edges are not discussed. |
I have developed a few tests for the |
I'm too overwhelmed to take a deep look, but I seem to remember coming to a similar conclusion and correcting these issues in the C core. Eventually (hopefully soon) Here's the C documentation where I typed up how normalization works at one point:
This should explain what normalization was used for the old version (what |
It would be nice to have a function Then the laplace_matrix could also be defined as L = BWBT. Where BT is the transpose of B, and W is the the diagonal weight matrix |
I believe this is the reason for the failures in countland. We identified this as the only package for which we know that tests are failing and where the failures aren't handled one way or another. igraph 1.6.0requireNamespace("Matrix")
#> Loading required namespace: Matrix
mat <- rbind(
c(116, 210, 200),
c(210, 386, 380),
c(200, 380, 401)
)
A <- as(mat, "dgCMatrix")
Ai <- igraph::as.undirected(igraph::graph.adjacency(A, weighted = T))
Ai
#> IGRAPH f882c58 U-W- 3 6 --
#> + attr: weight (e/n)
#> + edges from f882c58:
#> [1] 1--1 1--2 2--2 1--3 2--3 3--3
L <- igraph::laplacian_matrix(Ai, normalized = T)
L
#> 3 x 3 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 1.0000000 -0.4269739 -0.4101324
#> [2,] -0.4269739 1.0000000 -0.6495964
#> [3,] -0.4101324 -0.6495964 1.0000000 Created on 2024-01-23 with reprex v2.1.0 igraph 1.99.99requireNamespace("Matrix")
#> Loading required namespace: Matrix
mat <- rbind(
c(116, 210, 200),
c(210, 386, 380),
c(200, 380, 401)
)
A <- as(mat, "dgCMatrix")
Ai <- igraph::as.undirected(igraph::graph.adjacency(A, weighted = T))
#> Warning: `graph.adjacency()` was deprecated in igraph 2.0.0.
#> ℹ Please use `graph_from_adjacency_matrix()` instead.
#> This warning is displayed once every 8 hours.
#> Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
#> generated.
Ai
#> IGRAPH 6fdb7b3 U-W- 3 6 --
#> + attr: weight (e/n)
#> + edges from 6fdb7b3:
#> [1] 1--1 1--2 2--2 1--3 2--3 3--3
L <- igraph::laplacian_matrix(Ai, normalized = T)
L
#> 3 x 3 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.7794677 -0.2930903 -0.2784214
#> [2,] -0.2930903 0.6045082 -0.3883508
#> [3,] -0.2784214 -0.3883508 0.5912334 Created on 2024-01-23 with reprex v2.1.0 CC @shchurch. |
@clpippel: Would you like to post your tests here? Happy to embed them. |
Results are the same for the unnormalized case, though. I'll mark this a breaking change because I don't see how to make the current code compatible with the old implementation. requireNamespace("Matrix")
#> Loading required namespace: Matrix
mat <- rbind(
c(116, 210, 200),
c(210, 386, 380),
c(200, 380, 401)
)
A <- as(mat, "dgCMatrix")
Ai <- igraph::as.undirected(igraph::graph.adjacency(A, weighted = T))
#> Warning: `graph.adjacency()` was deprecated in igraph 2.0.0.
#> ℹ Please use `graph_from_adjacency_matrix()` instead.
#> This warning is displayed once every 8 hours.
#> Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
#> generated.
Ai
#> IGRAPH dd41cdb U-W- 3 6 --
#> + attr: weight (e/n)
#> + edges from dd41cdb:
#> [1] 1--1 1--2 2--2 1--3 2--3 3--3
L <- igraph::laplacian_matrix(Ai, normalized = FALSE)
L
#> 3 x 3 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 820 -420 -400
#> [2,] -420 1180 -760
#> [3,] -400 -760 1160 Created on 2024-01-23 with reprex v2.1.0 |
Graphs
Tests
Graphs g5, g6 fail. |
@krlmlr This change is actually a bugfix in the handling of self-loops. When self-loops are present, the diagonal of the Laplacian As I recall, the bugfix applies to both normalized and non-normalized versions (both were wrong IIRC). |
Here's what I suggest we should do with
|
Something to pay attention to is that R/igraph is still not exposing the loop-control feature of |
I tried in R/igraph:
Function degree(), laplacian_matrix() assumes 2, 0 respectively. |
The implementation of
laplacian_matrix()
in 2.0 looks at least suspicious to me. This function does not have tests at the moment. Adding tests that check that nothing changed since 1.6.0 should be a priority.Dense and sparse cases should both be tested
The text was updated successfully, but these errors were encountered: