Back to Search
Start Over
Kemeny's constant for non-backtracking random walks
- 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.
- Subjects :
- Mathematics - Combinatorics
05C50, 05C81
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2203.12049
- Document Type :
- Working Paper