论文标题
凯门尼（Kemeny）的不可追踪随机步行
Kemeny's constant for non-backtracking random walks
论文作者
论文摘要
Kemeny的连接图$ G $的常数是随机步行到随机选择的顶点$ u $的预期时间，而不论初始顶点的选择如何。我们将Kemeny常数的定义扩展到非折线随机步行，并将其与凯门尼的常数进行比较，以进行简单的随机步行。我们探讨了几个图的这两个参数之间的关系，并为常规图和双重图提供了封闭形式的表达式。在几乎所有情况下，非背带变体都会产生较小的凯门尼常数。
Kemeny's constant for a connected graph $G$ is the expected time for a random walk to reach a randomly-chosen vertex $u$, regardless of the choice of the initial vertex. We extend the definition of Kemeny's constant to non-backtracking random walks and compare it to Kemeny's constant for simple random walks. We explore the relationship between these two parameters for several families of graphs and provide closed-form expressions for regular and biregular graphs. In nearly all cases, the non-backtracking variant yields the smaller Kemeny's constant.
