Sgtcheegerconstant constant by a sweep over the Fiedler vector

Formula: h(G) = min_S |boundary(S)| / min(vol S, vol S^c); lambda_2/2 <= h(G) <= sqrt(2 lambda_2) for the NORMALISED Laplacian I - D^-1/2 A D^-1/2

Usage

Sgtcheegerconstant(A)

Arguments

A

See Usage.

Value

List with sweep_min, lower_bound (lambda_2/2), upper_bound (sqrt(2 lambda_2)), lambda2, cut_set, fiedler, n.

References

Sgtcheegerconstant (1970), A lower bound for the smallest eigenvalue of the Laplacian, in Problems in Analysis; Chung (1997), Spectral Graph Theory, AMS. Neither is held locally; the conductance definition and the sweep-cut construction are standard published results. The sweep value is checked against exhaustive enumeration over all subsets in the batch's anchor file.

Examples

A <- matrix(c(4, 1, 0.5, 1, 3, 0.8, 0.5, 0.8, 2), nrow = 3)
res <- Sgtcheegerconstant(A = A)
res
#> $sweep_min
#> [1] 1
#> 
#> $lower_bound
#> [1] 0.6757037
#> 
#> $upper_bound
#> [1] 1.644024
#> 
#> $lambda2
#> [1] 1.351407
#> 
#> $cut_set
#> [1] 0
#> 
#> $fiedler
#> [1] -0.49902009 -0.08078592  0.68764983
#> 
#> $n
#> [1] 3
#> 
#> $method
#> [1] "Sgtcheegerconstant constant (Fiedler sweep upper bound)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"