A centrality measure of the cut-edges of an undirected graph, given in Altafini et al. (SIAM J. Matrix Anal. Appl. 44(2), 648–669 2023) and based on Kemeny’s constant, is revisited. A numerically more stable expression is given to compute this measure, and an explicit expression is provided for some classes of graphs, including one-path graphs and trees formed by three or more branches. These results theoretically confirm the good physical behaviour of this centrality measure, experimentally observed in Altafini et al. (SIAM J. Matrix Anal. Appl. 44(2), 648–669 2023). Numerical tests are reported to check the stability and to confirm the good physical behaviour.
Cut-edge centralities in an undirected graph
Bini D. A.;Latouche G.;Meini B.
2025-01-01
Abstract
A centrality measure of the cut-edges of an undirected graph, given in Altafini et al. (SIAM J. Matrix Anal. Appl. 44(2), 648–669 2023) and based on Kemeny’s constant, is revisited. A numerically more stable expression is given to compute this measure, and an explicit expression is provided for some classes of graphs, including one-path graphs and trees formed by three or more branches. These results theoretically confirm the good physical behaviour of this centrality measure, experimentally observed in Altafini et al. (SIAM J. Matrix Anal. Appl. 44(2), 648–669 2023). Numerical tests are reported to check the stability and to confirm the good physical behaviour.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
