WEIGHTED ENUMERATION OF NONBACKTRACKING WALKS ON WEIGHTED GRAPHS
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
Major/Subject
Mcode
Degree programme
Language
en
Pages
22
Series
SIAM Journal on Matrix Analysis and Applications, Volume 45, issue 1, pp. 397-418
Abstract
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.Description
Publisher Copyright: © 2024 Society for Industrial and Applied Mathematics.
Other note
Citation
Arrigo, F, Higham, D J, Noferini, V & Wood, R 2024, 'WEIGHTED ENUMERATION OF NONBACKTRACKING WALKS ON WEIGHTED GRAPHS', SIAM Journal on Matrix Analysis and Applications, vol. 45, no. 1, pp. 397-418. https://doi.org/10.1137/23M155219X