On the exponential generating function for non-backtracking walks

Francesca Arrigo, Peter Grindrod, Desmond J. Higham, Vanni Noferini

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

We derive an explicit formula for the exponential generating function associated with non-backtracking walks around a graph. We study both undirected and directed graphs. Our results allow us to derive computable expressions for nonbacktracking versions of network centrality measures based on the matrix exponential.We find that eliminating backtracking walks in this context does not significantly increase the computational expense. We show how the new measures may be interpreted in terms of standard exponential centrality computation on a certain multilayer network. Insights from this block matrix interpretation also allow us to characterize centrality measures arising from general matrix functions. Rigorous analysis on the star graph illustrates the effect of non-backtracking and shows that unwanted localization effects can be eliminated when we restrict to non-backtracking walks. We also investigate the localization issue on synthetic networks.
LanguageEnglish
Pages381-399
Number of pages19
JournalLinear Algebra and its Applications
Volume556
Early online date26 Jul 2018
DOIs
Publication statusPublished - 1 Nov 2018

Fingerprint

Exponential Generating Function
Exponential functions
Centrality
Walk
Star Graph
Matrix Exponential
Backtracking
Block Matrix
Directed graphs
Matrix Function
Undirected Graph
Directed Graph
Stars
Multilayer
Explicit Formula
Multilayers
Graph in graph theory

Keywords

  • centrality
  • matrix function
  • localization
  • network science

Cite this

Arrigo, Francesca ; Grindrod, Peter ; Higham, Desmond J. ; Noferini, Vanni. / On the exponential generating function for non-backtracking walks. In: Linear Algebra and its Applications. 2018 ; Vol. 556. pp. 381-399.
@article{a490a32f73e04ceb8924df9ba2b8fc9a,
title = "On the exponential generating function for non-backtracking walks",
abstract = "We derive an explicit formula for the exponential generating function associated with non-backtracking walks around a graph. We study both undirected and directed graphs. Our results allow us to derive computable expressions for nonbacktracking versions of network centrality measures based on the matrix exponential.We find that eliminating backtracking walks in this context does not significantly increase the computational expense. We show how the new measures may be interpreted in terms of standard exponential centrality computation on a certain multilayer network. Insights from this block matrix interpretation also allow us to characterize centrality measures arising from general matrix functions. Rigorous analysis on the star graph illustrates the effect of non-backtracking and shows that unwanted localization effects can be eliminated when we restrict to non-backtracking walks. We also investigate the localization issue on synthetic networks.",
keywords = "centrality, matrix function, localization, network science",
author = "Francesca Arrigo and Peter Grindrod and Higham, {Desmond J.} and Vanni Noferini",
year = "2018",
month = "11",
day = "1",
doi = "10.1016/j.laa.2018.07.010",
language = "English",
volume = "556",
pages = "381--399",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",

}

On the exponential generating function for non-backtracking walks. / Arrigo, Francesca; Grindrod, Peter; Higham, Desmond J.; Noferini, Vanni.

In: Linear Algebra and its Applications, Vol. 556, 01.11.2018, p. 381-399.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the exponential generating function for non-backtracking walks

AU - Arrigo, Francesca

AU - Grindrod, Peter

AU - Higham, Desmond J.

AU - Noferini, Vanni

PY - 2018/11/1

Y1 - 2018/11/1

N2 - We derive an explicit formula for the exponential generating function associated with non-backtracking walks around a graph. We study both undirected and directed graphs. Our results allow us to derive computable expressions for nonbacktracking versions of network centrality measures based on the matrix exponential.We find that eliminating backtracking walks in this context does not significantly increase the computational expense. We show how the new measures may be interpreted in terms of standard exponential centrality computation on a certain multilayer network. Insights from this block matrix interpretation also allow us to characterize centrality measures arising from general matrix functions. Rigorous analysis on the star graph illustrates the effect of non-backtracking and shows that unwanted localization effects can be eliminated when we restrict to non-backtracking walks. We also investigate the localization issue on synthetic networks.

AB - We derive an explicit formula for the exponential generating function associated with non-backtracking walks around a graph. We study both undirected and directed graphs. Our results allow us to derive computable expressions for nonbacktracking versions of network centrality measures based on the matrix exponential.We find that eliminating backtracking walks in this context does not significantly increase the computational expense. We show how the new measures may be interpreted in terms of standard exponential centrality computation on a certain multilayer network. Insights from this block matrix interpretation also allow us to characterize centrality measures arising from general matrix functions. Rigorous analysis on the star graph illustrates the effect of non-backtracking and shows that unwanted localization effects can be eliminated when we restrict to non-backtracking walks. We also investigate the localization issue on synthetic networks.

KW - centrality

KW - matrix function

KW - localization

KW - network science

UR - https://journals.elsevier.com/linear-algebra-and-its-applications

U2 - 10.1016/j.laa.2018.07.010

DO - 10.1016/j.laa.2018.07.010

M3 - Article

VL - 556

SP - 381

EP - 399

JO - Linear Algebra and its Applications

T2 - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

ER -