OJDM  Vol.6 No.4 , October 2016
Non-Backtracking Random Walks and a Weighted Ihara’s Theorem
Abstract: We study the mixing rate of non-backtracking random walks on graphs by looking at non-backtracking walks as walks on the directed edges of a graph. A result known as Ihara’s Theorem relates the adjacency matrix of a graph to a matrix related to non-backtracking walks on the directed edges. We prove a weighted version of Ihara’s Theorem which relates the transition probability matrix of a non-backtracking walk to the transition matrix for the usual random walk. This allows us to determine the spectrum of the transition probability matrix of a non-backtracking random walk in the case of regular graphs and biregular graphs. As a corollary, we obtain a result of Alon et al. in [1] that in most cases, a non-backtracking random walk on a regular graph has a faster mixing rate than the usual random walk. In addition, we obtain an analogous result for biregular graphs.
Cite this paper: Kempton, M. (2016) Non-Backtracking Random Walks and a Weighted Ihara’s Theorem. Open Journal of Discrete Mathematics, 6, 207-226. doi: 10.4236/ojdm.2016.64018.

[1]   Alon, N., Benjamini, I., Lubetzky, E. and Sodin, S. (2007) Non-Backtracking Random Walks Mix Faster. Communications in Contemporary Mathematics, 9, 585.

[2]   Lovász, L. (1993) Random Walks on Graphs: A Survey. Combinatorics, Paul ErdÖs is Eighty (Volume 2), Keszthely (Hungary), 1-46.

[3]   Chung, F. (1997) Spectral Graph Theory. AMS Publications, Boston.

[4]   Angel, O., Friedman, J. and Hoory, S. (2015) The Non-Backtracking Spectrum of the Universal Cover of a Graph. Transactions of the American Mathematical Society, 326, 4287-4318.

[5]   Fitzner, R. and van der Hofstad, R. (2013) Non-Backtracking Random Walk. Journal of Statistical Physics, 150, 264-284.

[6]   Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborova, L. and Zhang, P. (2013) Spectral Redemption in Clustering Sparse Networks. Proceedings of the National Academy of Sciences, 110, 20935-20940.

[7]   Ihara, Y. (1966) On Discrete Subgroups of the Two by Two Projective Linear Group over p-adic Fields. Journal of the Mathematical Society of Japan, 18, 219-235.

[8]   Hishimoto, K. (1992) Artin-Type L-Functinos and the Density Theorem for Prime Cycles on Finite Graphs. International Journal of Mathematics, 3, 809-826.

[9]   Bass, H. (1992) The Ihara-Selberg Zeta Function of a Tree Lattice. International Journal of Mathematics, 3, 717-797.

[10]   Stark, H.M. and Terras, A.A. (1996) Zeta Functions of Finite Graphs and Coverings. Advances in Mathematics, 121, 124-165.

[11]   Kotani, M. and Sunada, T. (2000) Zeta Functions of Finite Graphs. Journal of Mathematical Sciences, 7, 7-25.

[12]   Chung, F. (2005) Laplacians and the Cheeger Inequality for Directed Graphs. Annals of Combinatorics, 9, 1-19.

[13]   Nilli, A. (1991) On the Second Eigenvalue of a Graph. Discrete Mathematics, 91, 207-210.

[14]   Feng, K. and Li, W.-C.W. (1996) Spectra of Hypergraphs and Applications. Journal of Number Theory, 60, 1-22.

[15]   Li, W.-C.W. and Solé, P. (1996) Spectra of Regular Graphs and Hypergraphs and Orthogonal Polynomials. European Journal of Combinatorics, 17, 461-477.