Weighted enumeration of nonbacktracking walks on weighted graphs

Tools

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]
Preview
 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

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.

ORCID iDs

Arrigo, Francesca ORCID logoORCID: https://orcid.org/0000-0001-5473-7284, Higham, Desmond J. ORCID logoORCID: https://orcid.org/0000-0002-6635-3461, Noferini, Vanni and Wood, Ryan;
  • Item type:Article
    ID code:87056
    Dates:
    Date
    Event
    31 March 2024
    Published
    30 January 2024
    Published Online
    15 September 2023
    Accepted
    9 February 2023
    Submitted
    Subjects:Science > Mathematics > Analysis
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:25 Oct 2023 13:15
    Last modified:11 Nov 2024 14:06
    URI:https://strathprints.strath.ac.uk/id/eprint/87056
CORE (COnnecting REpositories)