WEIGHTED ENUMERATION OF NONBACKTRACKING WALKS ON WEIGHTED GRAPHS

Francesca Arrigo; Desmond J. Higham; Vanni Noferini; Ryan Wood

doi:10.1137/23M155219X

WEIGHTED ENUMERATION OF NONBACKTRACKING WALKS ON WEIGHTED GRAPHS

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

^*Corresponding author for this work

University of Strathclyde
University of Edinburgh

Research output: Contribution to journal › Article › Scientific › peer-review

3 Citations (Scopus)

144 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 language	English
Pages (from-to)	397-418
Number of pages	22
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	45
Issue number	1
DOIs	https://doi.org/10.1137/23M155219X
Publication status	Published - 2024
MoE publication type	A1 Journal article-refereed

Funding

Funding: The work of the first author was supported by fellowship ECF-2018-453 from the Leverhulme Trust. The work of the second author was supported the Engineering and Physical Sciences Research Council under grants EP/P020720/1 and EP/V015605/1. The third author was supported by an Academy of Finland grant (Suomen Akatemian päätös 331230). The fourth author was supported by an Academy of Finland grant (Suomen Akatemian päätös 331240)

Keywords

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

Access to Document

10.1137/23M155219X

Weighted Enumeration of Nonbacktracking Walks on Weighted GraphsFinal published version, 2.37 MB

Cite this

@article{30b77b47b55f4bb390672a2f392db4e4,

title = "WEIGHTED ENUMERATION OF NONBACKTRACKING WALKS ON WEIGHTED GRAPHS",

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.",

keywords = "centrality measure, combinatorics, complex network, evolving graph, generating function, Katz centrality, line graph, matrix function, temporal network",

author = "Francesca Arrigo and Higham, \{Desmond J.\} and Vanni Noferini and Ryan Wood",

note = "Publisher Copyright: {\textcopyright} 2024 Society for Industrial and Applied Mathematics.",

year = "2024",

doi = "10.1137/23M155219X",

language = "English",

volume = "45",

pages = "397--418",

journal = "SIAM Journal on Matrix Analysis and Applications",

issn = "0895-4798",

publisher = "Society for Industrial and Applied Mathematics",

number = "1",

}

TY - JOUR

T1 - WEIGHTED ENUMERATION OF NONBACKTRACKING WALKS ON WEIGHTED GRAPHS

AU - Arrigo, Francesca

AU - Higham, Desmond J.

AU - Noferini, Vanni

AU - Wood, Ryan

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

KW - centrality measure

KW - combinatorics

KW - complex network

KW - evolving graph

KW - generating function

KW - Katz centrality

KW - line graph

KW - matrix function

KW - temporal network

UR - https://www.scopus.com/pages/publications/85186640051

U2 - 10.1137/23M155219X

DO - 10.1137/23M155219X

M3 - Article

AN - SCOPUS:85186640051

SN - 0895-4798

VL - 45

SP - 397

EP - 418

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 1

ER -

WEIGHTED ENUMERATION OF NONBACKTRACKING WALKS ON WEIGHTED GRAPHS

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Noferini_Vanni_AoF_Project: Noferini Vanni Academy Project

Cite this

WEIGHTED ENUMERATION OF NONBACKTRACKING WALKS ON WEIGHTED GRAPHS

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Noferini_Vanni_AoF_Project: Noferini Vanni Academy Project

Cite this