Non-backtracking alternating walks

Francesca Arrigo, Desmond J. Higham, Vanni Noferini

Research output: Contribution to journalArticle

Abstract

The combinatorics of walks on a graph is a key topic in network science. Here we study a special class of walks on directed graphs. We combine two features that have previously been considered in isolation. We consider alternating walks, which form the basis of algorithms for hub/authority detection and for discovering directed bipartite substructure. Within this class, we restrict to non-backtracking walks, since this constraint has been seen to offer advantages in related contexts. We derive a recursive formula for counting the total number of non-backtracking alternating walks of a given length, leading to an expression for any associated power series expansion. We discuss computational issues for the widely used cases of resolvent and exponential series, showing that non-backtracking can be incorporated at very little extra cost. We also derive an appropriate asymptotic limit which gives a parameter-free, spectral analogue. We perform tests on an artificial data set in order to quantify the advantages of the new methodology. We also show that the removal of backtracking allows us to identify larger bipartite subgraphs within an anatomical connectivity network from neuroscience.
LanguageEnglish
Pages781–801
Number of pages21
JournalSIAM Journal on Applied Mathematics
Volume79
Issue number3
DOIs
Publication statusPublished - 9 May 2019

Fingerprint

Directed graphs
Walk
Costs
Power Series Expansion
Recursive Formula
Network Connectivity
Neuroscience
Asymptotic Limit
Backtracking
Substructure
Resolvent
Combinatorics
Directed Graph
Isolation
Subgraph
Counting
Quantify
Analogue
Series
Methodology

Keywords

  • bipartivity
  • centrality
  • directed graph
  • generating function
  • matrix polynomial
  • network

Cite this

Arrigo, Francesca ; Higham, Desmond J. ; Noferini, Vanni. / Non-backtracking alternating walks. In: SIAM Journal on Applied Mathematics . 2019 ; Vol. 79, No. 3. pp. 781–801.
@article{c98d2253d3534f8cb061b2c18b1f5d4a,
title = "Non-backtracking alternating walks",
abstract = "The combinatorics of walks on a graph is a key topic in network science. Here we study a special class of walks on directed graphs. We combine two features that have previously been considered in isolation. We consider alternating walks, which form the basis of algorithms for hub/authority detection and for discovering directed bipartite substructure. Within this class, we restrict to non-backtracking walks, since this constraint has been seen to offer advantages in related contexts. We derive a recursive formula for counting the total number of non-backtracking alternating walks of a given length, leading to an expression for any associated power series expansion. We discuss computational issues for the widely used cases of resolvent and exponential series, showing that non-backtracking can be incorporated at very little extra cost. We also derive an appropriate asymptotic limit which gives a parameter-free, spectral analogue. We perform tests on an artificial data set in order to quantify the advantages of the new methodology. We also show that the removal of backtracking allows us to identify larger bipartite subgraphs within an anatomical connectivity network from neuroscience.",
keywords = "bipartivity, centrality, directed graph, generating function, matrix polynomial, network",
author = "Francesca Arrigo and Higham, {Desmond J.} and Vanni Noferini",
year = "2019",
month = "5",
day = "9",
doi = "10.1137/18M1183698",
language = "English",
volume = "79",
pages = "781–801",
journal = "SIAM Journal on Applied Mathematics",
issn = "0036-1399",
number = "3",

}

Non-backtracking alternating walks. / Arrigo, Francesca; Higham, Desmond J.; Noferini, Vanni.

In: SIAM Journal on Applied Mathematics , Vol. 79, No. 3, 09.05.2019, p. 781–801.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Non-backtracking alternating walks

AU - Arrigo, Francesca

AU - Higham, Desmond J.

AU - Noferini, Vanni

PY - 2019/5/9

Y1 - 2019/5/9

N2 - The combinatorics of walks on a graph is a key topic in network science. Here we study a special class of walks on directed graphs. We combine two features that have previously been considered in isolation. We consider alternating walks, which form the basis of algorithms for hub/authority detection and for discovering directed bipartite substructure. Within this class, we restrict to non-backtracking walks, since this constraint has been seen to offer advantages in related contexts. We derive a recursive formula for counting the total number of non-backtracking alternating walks of a given length, leading to an expression for any associated power series expansion. We discuss computational issues for the widely used cases of resolvent and exponential series, showing that non-backtracking can be incorporated at very little extra cost. We also derive an appropriate asymptotic limit which gives a parameter-free, spectral analogue. We perform tests on an artificial data set in order to quantify the advantages of the new methodology. We also show that the removal of backtracking allows us to identify larger bipartite subgraphs within an anatomical connectivity network from neuroscience.

AB - The combinatorics of walks on a graph is a key topic in network science. Here we study a special class of walks on directed graphs. We combine two features that have previously been considered in isolation. We consider alternating walks, which form the basis of algorithms for hub/authority detection and for discovering directed bipartite substructure. Within this class, we restrict to non-backtracking walks, since this constraint has been seen to offer advantages in related contexts. We derive a recursive formula for counting the total number of non-backtracking alternating walks of a given length, leading to an expression for any associated power series expansion. We discuss computational issues for the widely used cases of resolvent and exponential series, showing that non-backtracking can be incorporated at very little extra cost. We also derive an appropriate asymptotic limit which gives a parameter-free, spectral analogue. We perform tests on an artificial data set in order to quantify the advantages of the new methodology. We also show that the removal of backtracking allows us to identify larger bipartite subgraphs within an anatomical connectivity network from neuroscience.

KW - bipartivity

KW - centrality

KW - directed graph

KW - generating function

KW - matrix polynomial

KW - network

UR - https://epubs.siam.org/loi/smjmap

U2 - 10.1137/18M1183698

DO - 10.1137/18M1183698

M3 - Article

VL - 79

SP - 781

EP - 801

JO - SIAM Journal on Applied Mathematics

T2 - SIAM Journal on Applied Mathematics

JF - SIAM Journal on Applied Mathematics

SN - 0036-1399

IS - 3

ER -