INdAM Workshop: Low-rank Structures and Numerical Methods in Matrix and Tensor Computations

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

Sep 1, 2025, 4:10 PM

1h 10m

Palazzone di Cortona

Poster Poster Session

Speaker

Dario Andrea Bini (Dipartimento di Matematica, Università di Pisa)

Description

Kemeny's constant is a global measure of closeness to non-connectivity of a graph [4], [5]. Its variation, after removing an edge $e$, has been used in [1] to define the centrality of the edge $e$ in an undirected graph. This measure, suitably modified, has been applied to cut-edges and an explicit expression has been provided for certain classes of graphs in [2]. Here, we propose a sort of directional derivative of the Kemeny constant as a measure of the edge centrality. We prove the positivity of this measure, provide an explicit expression in terms of the inverse of the modified graph Laplacian, show that it can also be applied to cut-edges with no modification, relate it to the measure of [1] and [2], and provide algorithms for its computation. Advantages with respect to the previous measures are discussed, and an application to the analysis of the road map of Pisa is shown.

References

1. D. Altafini, D. Bini, V. Cutini, B. Meini, F. Poloni, An edge centrality measure based on the Kemeny constant, SIMAX 44, 2023.

2. D. Bini, S. Kirkland, G. Latouche, B. Meini, Cut-edge centralities in an undirected graph, Numer. Algo. 2025

3. D. Bini, B. Meini, F. Poloni, The derivative of Kemeny’s constant as centrality measure in undirected graphs. In preparation.

4. J. Breen, E. Crisostomi, S. Kim, Kemeny's constant for a graph with bridges. Discrete Appl. Math. 2022.

5. E. Crisostomi, S. Kirkland, R. Shorten, A Google-like model of road network dynamics and its application to regulation and control. Internat. J. Control 2011.