Weighted Enumeration of Nonbacktracking Walks on Weighted Graphs

DOI10.1137/23M155219XarXiv2202.02888MaRDI QIDQ6154946FDOQ6154946

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)

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.

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

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

zbMATH Keywords

combinatoricsgenerating functioncomplex networkline graphmatrix functioncentrality measuretemporal networkevolving graphKatz centrality

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Generating functions of non-backtracking walks on weighted digraphs: radius of convergence and Ihara's theorem
• Maximal colourings for graphs

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)