The derivative of Kemeny’s constant as a centrality measure in undirected graphs

Abstract Kemeny’s constant quantifies a graph’s connectivity by measuring the average time for a random walker to reach any other vertex. We introduce two concepts of the directional derivative of Kemeny’s constant with respect to an edge and use them to define centrality measures for edges and nonedges in the graph. Additionally, we present a sensitivity measure of Kemeny’s constant. An explicit expression for these quantities involving the inverse of the modified graph Laplacian is provided, which is valid even for cut-edges. These measures are connected to the one introduced in Altafini, Bini, Cutini, Meini & Poloni (2023 An edge centrality measure based on the Kemeny constant. SIAM J. Matrix Anal. Appl., 44, 648–669.), and algorithms for their computation are included. The benefits of these measures are discussed, along with applications to road networks and link prediction analysis. For one-path graphs, an explicit expression for these measures is given in terms of the edge weights.