WEIGHTED ENUMERATION OF NONBACKTRACKING WALKS ON WEIGHTED GRAPHS

Francesca Arrigo, Desmond J. Higham, Vanni Noferini, Ryan Wood*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
24 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)397-418
Number of pages22
JournalSIAM Journal on Matrix Analysis and Applications
Volume45
Issue number1
DOIs
Publication statusPublished - 2024
MoE publication typeA1 Journal article-refereed

Keywords

  • centrality measure
  • combinatorics
  • complex network
  • evolving graph
  • generating function
  • Katz centrality
  • line graph
  • matrix function
  • temporal network

Fingerprint

Dive into the research topics of 'WEIGHTED ENUMERATION OF NONBACKTRACKING WALKS ON WEIGHTED GRAPHS'. Together they form a unique fingerprint.

Cite this