Eigenvectors of the normalised Laplacian for the k smallest values

Eigenvectors are sign-fixed on their largest-magnitude entry, without which the two language arms would disagree on an arbitrary sign. Under a repeated eigenvalue the individual vectors remain arbitrary within their eigenspace; only the eigenvalues and the projector are defined.

Usage

Lapeig(W, k = 2, tol = 1e-10)

Arguments

W

Symmetric non-negative weight matrix.

k

Number of eigenpairs returned (1 <= k <= n).

tol

An eigenvalue below this counts as zero.

Value

List with values, vectors, fiedler, lambda1, n_components, n, k.

Details

Formula: Lcal u = lambda u, lambda_0 <= ... <= lambda_{k-1}; Fiedler vector = u for the smallest lambda > tol

References

Chung (1997), Spectral Graph Theory, CBMS 92, Section 1.2, which writes Lcal as an operator on functions g : V -> R and works with its harmonic eigenfunctions.

Examples

W <- matrix(0, 6, 6); W[1:3, 1:3] <- 1; W[4:6, 4:6] <- 1; W[3, 4] <- W[4, 3] <- 0.1; diag(W) <- 0
e <- Lapeig(W, k = 2)
sign(e$fiedler)   # splits the two triangles
#> [1] -1 -1 -1  1  1  1