Weighted enumeration of nonbacktracking walks on weighted graphs

Arrigo, Francesca and Higham, Desmond J. and Noferini, Vanni and Wood, Ryan (2024) Weighted enumeration of nonbacktracking walks on weighted graphs. SIAM Journal on Matrix Analysis and Applications, 45 (1). pp. 397-418. ISSN 0895-4798 (https://doi.org/10.1137/23M155219X)

[thumbnail of Arrigo-etal-SJMAA-2023-Weighted-enumeration-of-nonbacktracking-walks-on-weighted-graphs]
Text. Filename: Arrigo_etal_SJMAA_2023_Weighted_enumeration_of_nonbacktracking_walks_on_weighted_graphs.pdf
Accepted Author Manuscript
License: Creative Commons Attribution 4.0 logo

Download (33MB)| Preview


We extend the notion of nonbacktracking walks from unweighted graphs to graphs whose edges have a nonnegative weight. Here the weight associated with a walk is taken to be the product over the weights along the individual edges. We give two ways to compute the associated generating function, and corresponding node centrality measures. One method works directly on the original graph and one uses a line graph construction followed by a projection. The first method is more efficient, but the second has the advantage of extending naturally to time-evolving graphs. Based on these generating functions, we define and study corresponding centrality measures. Illustrative computational results are also provided.