Article citationsMore>>

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.
http://dx.doi.org/10.1073/pnas.1312486110

has been cited by the following article:

• TITLE: Non-Backtracking Random Walks and a Weighted Ihara’s Theorem

  AUTHORS: Mark Kempton

  KEYWORDS: Graph, Random Walk, Non-Backtracking Random Walk, Ihara Zeta Identity, Mixing Rate

  JOURNAL NAME: Open Journal of Discrete Mathematics, Vol.6 No.4, August 16, 2016

  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.