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.

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

Dario Bini;BEATRICE MEINI;Federico Poloni
2026-01-01

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.
2026
Bini, Dario; Meini, Beatrice; Poloni, Federico
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1377388
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact