Random-walk kernel of a graph as a resolvent

sum_k lam^k A^k counts walks of every length with a geometric discount and equals (I - lam A)^{-1} exactly when the series converges, i.e. when lam is below the reciprocal spectral radius. Computing the resolvent instead of truncating the series is not an optimisation: a truncation at K terms is a different kernel.

Usage

Sgtrwk(A, lam = 0.1)

Arguments

A

Adjacency matrix.

lam

Discount, positive and small enough for convergence.

Value

List with K, estimate (sum of all entries), trace, n.

Details

Formula: K = sum_{k>=0} lam^k A^k = (I - lam A)^{-1}.

References

Gaertner, T., Flach, P. & Wrobel, S. (2003). On graph kernels: hardness results and efficient alternatives. Learning Theory and Kernel Machines, LNCS 2777, pages 129-143. doi:10.1007/978-3-540-45167-9_11 .

Examples

A <- matrix(c(4, 1, 0.5, 1, 3, 0.8, 0.5, 0.8, 2), nrow = 3)
res <- Sgtrwk(A = A)
res
#> $K
#>           [,1]      [,2]      [,3]
#> [1,] 1.7213395 0.2611859 0.1337023
#> [2,] 0.2611859 1.4847175 0.1647959
#> [3,] 0.1337023 0.1647959 1.2748360
#> 
#> $estimate
#> [1] 5.600261
#> 
#> $trace
#> [1] 4.480893
#> 
#> $n
#> [1] 3
#> 
#> $method
#> [1] "Random-walk kernel (I - lam A)^{-1}"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"