Conductance of a hot-spot set and the Cheeger bound on the spectral gap

For a weighted street graph (symmetric non-negative adjacency) and a set of places S, reports the conductance \(h(S) = \mathrm{cut}(S)/\min(\mathrm{vol}\,S, \mathrm{vol}\,S^c)\), the Rayleigh quotient of the two-valued test vector, which equals \(\mathrm{cut}(S)(1/\mathrm{vol}\,S + 1/\mathrm{vol}\,S^c)\) (Research.P3.rayleigh_testVec), and the second eigenvalue \(\lambda_2\) of the normalised Laplacian. The proved chain is \(\lambda_2 \le E(f)/D(f) \le 2h(S)\) (cheeger_easy): a set that few patrol-crossings leave relative to its volume forces a small spectral gap, so anything that diffuses along the graph (displacement, spillover) leaves such a set slowly. With exhaustive = TRUE on a small graph the Cheeger constant \(h_G = \min_S h(S)\) is found by enumeration.

Usage

morie_cheeger_bound(adjacency, S, exhaustive = FALSE)

Arguments

adjacency: Square symmetric matrix of non-negative weights.
S: Indices (or a logical vector) of the places in the set.
exhaustive: Also minimise \(h(S)\) over every non-trivial subset (graphs with at most 16 places).

Value

A list with cut, vol_S, vol_complement, conductance, rayleigh_test, lambda2, bound_holds (\(\lambda_2 \le E(f)/D(f) \le 2h(S)\)), cheeger_constant and argmin_set when exhaustive, and theorems.

Examples

# two dense blocks joined by one edge
A <- matrix(0, 6, 6)
A[1, 2] <- A[1, 3] <- A[2, 3] <- A[4, 5] <- A[4, 6] <- A[5, 6] <- A[3, 4] <- 1
A <- A + t(A)
morie_cheeger_bound(A, S = 1:3)[c("conductance", "rayleigh_test", "lambda2", "bound_holds")]
#> $conductance
#> [1] 0.1428571
#> 
#> $rayleigh_test
#> [1] 0.2857143
#> 
#> $lambda2
#> [1] 0.2046664
#> 
#> $bound_holds
#> [1] TRUE
#>