Each undirected edge becomes two directed edges; for e = (u, v) and
f = (w, x), \(B_{ef} = 1\) iff v = w and x != u. Powers of B
count non-backtracking walks, which is why its spectrum drives
clustering in sparse graphs where the adjacency spectrum fails.
Usage
morie_nonbacktracking_matrix(edges, n = NULL)
Arguments
- edges
Two-column matrix or list of pairs (undirected).
- n
Optional number of nodes.
Value
Named list with B, directed_edges (two-column
matrix, row order of B), n, m, method.
Details
Mirrors morie.fn.sgtnbe.
References
Hashimoto, K. (1989). Zeta functions of finite graphs
and representations of p-adic groups. Adv. Stud. Pure
Math., 15, 211-280. Krzakala, F. et al. (2013). Spectral
redemption in clustering sparse networks. PNAS, 110(52),
20935-20940.
Examples
morie_nonbacktracking_matrix(rbind(c(0, 1), c(1, 2)))$m
#> [1] 2
