05C50 Online Seminar: Beatrice Meini

Given a connected undirected graph G = (V,E), where V is the set of vertices and E the set of edges (possibly with weights), denote by A the associated adjacency matrix. The Kemeny constant of the graph G is defined as the Kemeny constant of the Markov chain with transition matrix P, where P is obtained by scaling the rows of A to obtain a stochastic matrix.

The Kemeny constant gives a global measure of the non-connectivity of a network . Indeed, if G is not connected then the Kemeny constant cannot be defined or, in different words, it takes the value infinity. We introduce and analyze a definition of edge centrality, based on the variation of the Kemeny constant.

More precisely, we may formally define the Kemeny-based centrality score of an adge as the change of the connectivity of the graph measured by the Kemeny constant, when such edge is removed from the graph itself. A drawback of this definition of centrality score is that there exist graphs where the score is negative for some edge. In the literature, this fact is known as the Braess paradox. To overcome this drawback we propose a modified centrality measure, which is nonnegative for any graph and for any edge. The underlying idea consists in replacing an edge with a loop at each vertex. By applying a corollary of the Courant-Fischer theorem we prove that the score is always nonnegative.

This definition cannot be applied in the case of a cut-edge. This drawback is solved by introducing the concept of regularized centrality score, depending on a regularization parameter. It is interesting to point out that the regularized approach can be applied also to graphs that are not connected.

We have designed effective algorithms implementing the computation of the score of a single edge, or of all the edges of a graph. Our algorithms have been tested both on synthetic graphs and on graphs representing real road networks, in particular, we have considered the maps of Pisa and of the entire Tuscany. From our numerical experiments, it turned out that this measure is robust, effective, and realistic from the model point of view. Indeed, our model succeeds in detecting bridges on the river Arno and overpasses over the railroad line as important roads in the Pisa road map. Moreover, the computation is sufficiently fast even for large road networks.

More details can be found in the paper D.Altafini, D.A. Bini, V. Cutini, B. Meini, and F. Poloni.

An edge centrality score based on the Kemeny constant. SIAM J. Matrix Anal. Appl., 2023