Back to Search Start Over

Kemeny's constant for non-backtracking random walks

Authors :
Breen, Jane
Faught, Nolan
Glover, Cory
Kempton, Mark
Knudson, Adam
Oveson, Alice
Publication Year :
2022

Abstract

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.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2203.12049
Document Type :
Working Paper