A theory for backtrack-downweighted walks

FRANCESCA ARRIGO, DESMOND J. HIGHAM, VANNI NOFERINI

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
20 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)1229-1247
Number of pages19
JournalSIAM Journal on Matrix Analysis and Applications
Volume42
Issue number3
DOIs
Publication statusPublished - 2021
MoE publication typeA1 Journal article-refereed

Keywords

  • Centrality index
  • Complex network
  • Generating function
  • Localization
  • Nonbacktracking walk
  • Zeta function

Fingerprint

Dive into the research topics of 'A theory for backtrack-downweighted walks'. Together they form a unique fingerprint.

Cite this