On the Edge Derivative of the Normalized Laplacian with Applications to Kemeny's Constant

2022/11/02 by Connor Albright, Kimberly P. Hadaway, Albright, Connor +9 · 2 citations
Engineering · Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Surface Chemistry and Catalysis

paper · pdf · doi:10.48550/arxiv.2211.01495

openalex publication_date 2022/11/02 · openalex created_date 2022/11/09 · openalex updated_date 2026/07/28

Abstract

In a connected graph, Kemeny's constant gives the expected time of a random walk from an arbitrary vertex x to reach a randomly-chosen vertex y. Because of this, Kemeny's constant can be interpreted as a measure of how well a graph is connected. It is generally unknown how the addition or removal of edges affects Kemeny's constant. Inspired by the directional derivative of the normalized Laplacian, we derive the directional derivative of Kemeny's constant for several graph families. In addition, we find sharp bounds for the directional derivative of an eigenvalue of the normalized Laplacian and bounds for the directional derivative of Kemeny's constant.

Cited by

• The Derivative of Kemeny's Constant as a Centrality Measure in Undirected Graphs
• Lipschitz Bounds for Persistent Laplacian Eigenvalues under One-Simplex Insertions

Related

• The Derivative of Kemeny's Constant as a Centrality Measure in Undirected Graphs
• Kemeny's constant for non-backtracking random walks
• Edge Addition and the Change in Kemeny's Constant
• A Spectral Approach to Kemeny's Constant
• On defining Kemeny's constant for non-backtracking random walks