An edge centrality measure based on the Kemeny constant

Altafini, Diego ORCID: https://orcid.org/0000-0002-6559-2372, Bini, Dario, Cutini, Valerio, Meini, Beatrice and Poloni, Federico 2023. An edge centrality measure based on the Kemeny constant. Siam Journal on Matrix Analysis and Applications 44 (2) , pp. 648-669. 10.1137/22M1486728

Preview

PDF - Accepted Post-Print Version Available under License Creative Commons Attribution. Download (3MB) | Preview

Abstract

A new measure of the centrality of an edge in an undirected graph is introduced. It is based on the variation of the Kemeny constant of the graph after removing the edge . The new measure is designed to satisfy certain monotonicity and positivity properties, and hence using it one can avoid the Braess paradox, i.e., the phenomenon in which removing an edge can increase the connectivity of a network rather than reduce it. A numerical method for computing is introduced, and a regularization technique is designed in order to deal with cut-edges and disconnected graphs. Numerical experiments performed both on artificial examples and on real road networks show that this measure is particularly effective in revealing bottleneck roads whose removal would greatly reduce the connectivity of the network.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Architecture
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	0895-4798
Date of First Compliant Deposit:	21 May 2024
Date of Acceptance:	28 November 2022
Last Modified:	10 Nov 2024 07:30
URI:	https://orca.cardiff.ac.uk/id/eprint/168512

Actions (repository staff only)

Edit Item