SOME RELATIONS BETWEEN THE SPECTRA OF SIMPLE AND NON-BACKTRACKING RANDOM WALKS
SOME RELATIONS BETWEEN THE SPECTRA OF SIMPLE AND NON-BACKTRACKING RANDOM WALKS
复制标题
简单随机游走谱和非回溯随机游走谱之间的一些关系
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
N. Anantharaman
中科院分区：
文献类型：
--
作者：
N. Anantharaman
我们建立了非正则图上简单随机游动和非回溯随机游动的谱之间的关系，推广了正则图上的一些著名事实。我们的两个主要结果是：1）简单随机游动和非回溯随机游动的混合率之间的定量关系; 2）“Ihara行列式公式“的一个变体，它将邻接矩阵或拉普拉斯算子的特征多项式表示为具有全纯权的非回溯随机游动的行列式.
We establish some relations between the spectra of simple and non-backtracking random walks on non-regular graphs, generalizing some well-known facts for regular graphs. Our two main results are 1) a quantitative relation between the mixing rates of the simple random walk and of the non-backtracking random walk 2) a variant of the " Ihara determinant formula " which expresses the characteristic polynomial of the adjacency matrix, or of the laplacian, as the determinant of a certain non-backtracking random walk with holomorphic weights.