Non-backtracking alternating walks

Tools

Arrigo, Francesca and Higham, Desmond J. and Noferini, Vanni (2019) Non-backtracking alternating walks. SIAM Journal on Applied Mathematics, 79 (3). 781–801. ISSN 1095-712X (https://doi.org/10.1137/18M1183698)

[thumbnail of Arrigo-etal-SIAM-JOAM-2019-Non-backtracking-alternating]
Preview
 Text. Filename: Arrigo_etal_SIAM_JOAM_2019_Non_backtracking_alternating.pdf
Accepted Author Manuscript
Download (1MB)| Preview

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.

ORCID iDs

Arrigo, Francesca ORCID logoORCID: https://orcid.org/0000-0001-5473-7284, Higham, Desmond J. ORCID logoORCID: https://orcid.org/0000-0002-6635-3461 and Noferini, Vanni;
CORE (COnnecting REpositories)