On defining Kemeny's constant for non-backtracking random walks

2025/10/08 by Jane Breen, Breen, Jane, Mark Kempton +5
Computer Science · Mathematics · #05C50 #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2510.06650

openalex publication_date 2025/10/08 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28

Abstract

We propose two possible definitions for a version of Kemeny's constant of a graph based on non-backtracking random walks (in place of the usual simple random walk). We show that these two definitions coincide for edge-transitive graphs, and give a condition generalizing edge-transitive for which equality holds, and investigate by how much they can differ in general. We compute our non-backtracking Kemeny's constant for several families of graphs.

Citations

• Effects of Backtracking on PageRank
• Kemeny's constant for non-backtracking random walks
• A 1-Separation Formula for the Graph Kemeny Constant and Braess Edges
• Hitting times for second-order random walks
• Spectral properties of the non-backtracking matrix of a graph
• Spanning 2-Forests and Resistance Distance in 2-Connected Graphs
• Non-backtracking random walks and a weighted Ihara's theorem

Related

• Kemeny's constant for non-backtracking random walks
• Threshold graphs, Kemeny's constant, and related random walk parameters
• A Spectral Approach to Kemeny's Constant
• A 1-Separation Formula for the Graph Kemeny Constant and Braess Edges
• The Derivative of Kemeny's Constant as a Centrality Measure in Undirected Graphs