The derivative of Kemeny’s constant as a centrality measure in undirected graphs
IMA Journal of Numerical Analysis · 18.08.2026
DOI: 10.1093/imanum/drag050 ↗Kurz gefasst
Fachartikel in der Zeitschrift IMA Journal of Numerical Analysis, online erschienen am 18.08.2026. Verfasst von Dario A Bini und 2 weiteren Autor:innen. Die Arbeit nennt 38 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Department of Mathematics, University of Pisa, European Union—NextGenerationEU, National Recovery and Resilience Plan (PNRR)—Mission 4 Education and research—Component 2 From.
Abstract (Originalsprache)
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.
Förderung
- Department of Mathematics, University of Pisa
- European Union—NextGenerationEU
- National Recovery and Resilience Plan (PNRR)—Mission 4 Education and research—Component 2 From
Zitieren
APA
Bini, D. A., Meini, B., & Poloni, F. (2026). The derivative of Kemeny’s constant as a centrality measure in undirected graphs. IMA Journal of Numerical Analysis. https://doi.org/10.1093/imanum/drag050
Vancouver
Bini DA, Meini B, Poloni F. The derivative of Kemeny’s constant as a centrality measure in undirected graphs. IMA Journal of Numerical Analysis. 2026. doi:10.1093/imanum/drag050
BibTeX
@article{Bini2026,
author = {Bini, Dario A and Meini, Beatrice and Poloni, Federico},
title = {The derivative of Kemeny’s constant as a centrality measure in undirected graphs},
journal = {IMA Journal of Numerical Analysis},
year = {2026},
doi = {10.1093/imanum/drag050}
}
EUVIMED