Laplacian eigenmaps: embed a graph in k dimensions

The trivial eigenvector D^{1/2} 1 at eigenvalue 0 carries no geometry and is dropped; the next k are the embedding. On a graph with c connected components eigenvalue 0 has multiplicity c, so a disconnected graph gives coordinates constant per component – the method behaving correctly, not a defect.

Usage

Sgtlap2(A, k = 2)

Arguments

A

Symmetric non-negative weight matrix.

k

Embedding dimension, 1 <= k <= n - 1.

Value

List with Y, eigvals, lambda1, k, n.

Details

Formula: L_sym = I - D^-1/2 A D^-1/2; Y is columns 2..k+1 of its eigenvectors, ordered by ascending eigenvalue.

References

Belkin, M. & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation 15(6):1373-1396. doi:10.1162/089976603321780317 .

Examples

A <- matrix(c(4, 1, 0.5, 1, 3, 0.8, 0.5, 0.8, 2), nrow = 3)
res <- Sgtlap2(A = A)
res
#> $Y
#>            [,1]       [,2]
#> [1,]  0.7362196 -0.2314496
#> [2,] -0.2755834  0.7557199
#> [3,] -0.6180894 -0.6126324
#> 
#> $eigvals
#> [1] 0.4441113 0.5975554
#> 
#> $lambda1
#> [1] -2.787716e-17
#> 
#> $k
#> [1] 2
#> 
#> $n
#> [1] 3
#> 
#> $method
#> [1] "Laplacian eigenmaps on L_sym"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"