EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Dario A Bini, Beatrice Meini, Federico Poloni

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →