期刊文献+
共找到1篇文章
< 1 >
每页显示 20 50 100
Non-Backtracking Random Walks and a Weighted Ihara’s Theorem
1
作者 Mark Kempton 《Open Journal of Discrete Mathematics》 2016年第4期207-226,共20页
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 ... 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. 展开更多
关键词 Graph Random Walk Non-Backtracking Random Walk ihara zeta identity Mixing Rate
下载PDF
上一页 1 下一页 到第
使用帮助 返回顶部