Weighted Enumeration of Nonbacktracking Walks on Weighted Graphs

DOI10.1137/23M155219XMaRDI QIDQ6154946zbMATH OpenFDO

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

Publication date 16 February 2024

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.02888

zbMATH Keywords

centrality measurecombinatoricscomplex networkevolving graphgenerating functionKatz centralityline graphmatrix functiontemporal network

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Signed and weighted graphs (05C22) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10)

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. Computational results are also provided.

Recommendations

• On the exponential generating function for non-backtracking walks
• A Theory for Backtrack-Downweighted Walks
• Non-backtracking walk centrality for directed networks
• Beyond non-backtracking: non-cycling network centrality measures
• Non-backtracking alternating walks

Cites work

• A new status index derived from sociometric analysis
• A zeta function with respect to non-backtracking alternating walks for a digraph
• An Ihara formula for partially directed graphs
• Beyond non-backtracking: non-cycling network centrality measures
• Block matrix formulations for evolving networks
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Dynamic Katz and related network measures
• scientific article; zbMATH DE number 3335806 (Why is no real title available?)
• Networks. An introduction.
• Non-backtracking PageRank
• Non-backtracking walk centrality for directed networks
• Nonbacktracking eigenvalues under node removal: X-centrality and targeted immunization
• On the exponential generating function for non-backtracking walks
• ON ZETA AND L-FUNCTIONS OF FINITE GRAPHS
• Similarity matrices for colored graphs
• The deformed graph Laplacian and its applications to network centrality analysis
• Zeta functions of digraphs
• Zeta functions of finite graphs and coverings

Cited in

(3)

• Generating functions of non-backtracking walks on weighted digraphs: radius of convergence and Ihara's theorem
• Maximal colourings for graphs
• Efficient computation of f-centralities and nonbacktracking centrality for temporal networks

This page was built for publication: Weighted Enumeration of Nonbacktracking Walks on Weighted Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154946)