Compute the Positive Spectrum of an Unweighted Graph Laplacian

Usage

graph.spectrum(
  graph,
  nev = NULL,
  use.R = FALSE,
  return.Laplacian = FALSE,
  return.dense = FALSE,
  tol = NULL
)

Arguments

graph: A dgraph; the final-stage topology defines the combinatorial Laplacian L = D - A. Stored edge lengths and attributes are not used.
nev: Number of smallest positive eigenpairs, in increasing eigenvalue order. NULL requests all n - nullity positive modes; zero requests none. Explicit counts must be integers in that range; they are never truncated.
use.R: Logical; use base R's dense symmetric eigensolver instead of the native backend. Both return the same numerical contract.
return.Laplacian: Logical; include the graph Laplacian in the result.
return.dense: Logical; return a base matrix when TRUE, otherwise a sparse Matrix object. If Matrix is unavailable, warn and return dense. Ignored when return.Laplacian = FALSE.
tol: Positive absolute eigenvalue tolerance. By default, use 100 * .Machine$double.eps * max(1, 2 * max.degree). Computed zero modes must have absolute eigenvalues at most tol; returned modes must exceed it. An unresolved separation from zero is an error, not silent truncation.

Value

A graph_spectrum list with evalues (the requested positive eigenvalues in increasing order), evectors (one row per original vertex, one orthonormal column per eigenvalue), nullity (the exact number of connected components), components (component IDs in vertex order), and the resolved tolerance. When requested, laplacian contains L. An empty or edgeless graph has no positive modes and an n by zero eigenvector matrix when nev = NULL or nev = 0.

Details

Every component contributes one zero mode, including isolated vertices. These modes are omitted from evalues and evectors; their number is determined from topology and checked against the computed spectrum. The native backend uses sparse Lanczos for partial spectra, requesting the component zero modes as well, and a dense eigensolver for the full spectrum. The R backend computes the full dense spectrum before selection. Thus a small explicit nev is preferable for large graphs. Dense solves require quadratic memory; requesting all positive modes is not a sparse operation.

Eigenvector signs and bases within repeated-eigenvalue subspaces are not unique. If nev or an embedding dimension cuts through a repeated eigenvalue, the selected subspace and embedding distances can differ between backends. Include the whole tied eigenspace for invariant comparisons.

Examples

graph <- create.graph("chain", 8)
spectrum <- graph.spectrum(graph, nev = 3)
spectrum$evalues
#> [1] 0.1522409 0.5857864 1.2346331
spectrum$nullity # one omitted zero mode
#> [1] 1
graph.spectral.embedding(spectrum, dim = 2)
#>             Dim1       Dim2
#> [1,] -0.49039264  0.4619398
#> [2,] -0.41573481  0.1913417
#> [3,] -0.27778512 -0.1913417
#> [4,] -0.09754516 -0.4619398
#> [5,]  0.09754516 -0.4619398
#> [6,]  0.27778512 -0.1913417
#> [7,]  0.41573481  0.1913417
#> [8,]  0.49039264  0.4619398