A theory for backtrack-downweighted walks
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2021
Major/Subject
Mcode
Degree programme
Language
en
Pages
19
1229-1247
1229-1247
Series
SIAM Journal on Matrix Analysis and Applications, Volume 42, issue 3
Abstract
We develop a complete theory for the combinatorics of walk-counting on a directed graph in the case where each backtracking step is downweighted by a given factor. By deriving expressions for the associated generating functions, we also obtain linear systems for computing centrality measures in this setting. In particular, we show that backtrack-downweighted Katz-style network centrality can be computed at the same cost as standard Katz. Studying the limit of this centrality measure at its radius of convergence also leads to a new expression for backtrackdownweighted eigenvector centrality that generalizes previous work to the case where directed edges are present. The new theory allows us to combine advantages of standard and nonbacktracking cases, avoiding localization while accounting for tree-like structures. We illustrate the behavior of the backtrack-downweighted centrality measure on both synthetic and real networks.Description
Funding Information: \ast Received by the editors December 7, 2020; accepted for publication (in revised form) May 6, 2021; published electronically August 5, 2021. https://doi.org/10.1137/20M1384725 \bfF \bfu \bfn \bfd \bfi \bfn \bfg : The work of the first author was supported by the fellowship ECF-2018-453 from the Leverhulme Trust. The work of the second author was supported by EPSRC Programme Grant EP/P020720/1. The work of the third author was supported by an Academy of Finland grant (Suomen Akatemian p\a"\a"to\"s 331240). \dagger Department of Mathematics and Statistics, University of Strathclyde, Glasgow, G1 1XH, UK (farrigo87@gmail.com). \ddagger School of Mathematics, University of Edinburgh, Edinburgh, EH9 3FD, UK (d.j.higham@ ed.ac.uk). \S Department of Mathematics and Systems Analysis, Aalto University, FI-00076, Aalto, Finland (vanni.noferini@aalto.fi). Publisher Copyright: © 2021 Society for Industrial and Applied Mathematics Publications. All rights reserved.
Keywords
Centrality index, Complex network, Generating function, Localization, Nonbacktracking walk, Zeta function
Other note
Citation
ARRIGO, FRANCESCA, HIGHAM, DESMOND J & NOFERINI, VANNI 2021, ' A theory for backtrack-downweighted walks ', SIAM Journal on Matrix Analysis and Applications, vol. 42, no. 3, pp. 1229-1247 . https://doi.org/10.1137/20M1384725