Beyond non-backtracking: non-cycling network centrality measures

Francesca Arrigo, Desmond J. Higham, Vanni Noferini

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)
56 Downloads (Pure)


Walks around a graph are studied in a wide range of fields, from graph theory and stochastic analysis to theoretical computer science and physics. In many cases it is of interest to focus on non-backtracking walks; those that do not immediately revisit their previous location. In the network science context,imposing a non-backtracking constraint on traditional walk-based node centrality measures is known to offer tangible benefits. Here, we use the Hashimoto matrix construction to characterize, generalize and study such non-backtracking centrality measures. We then devise a recursive extension that systematically removes triangles, squares and, generally, all cycles up to a given length. By characterizing the spectral radius of appropriate matrix power series, we explore how the universality results on the limiting behaviour of classical walk-based centrality measures extend to these non-cycling cases. We also demonstrate that the new recursive construction gives rise to practical centrality measures that can be applied to large scale networks.
Original languageEnglish
Article number20190653
Number of pages28
JournalProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
Issue number2235
Early online date11 Mar 2020
Publication statusPublished - 25 Mar 2020


  • centrality index
  • deformed graph Laplacian
  • Hashimoto matrix
  • complex network
  • matrix polynomial
  • generating function


Dive into the research topics of 'Beyond non-backtracking: non-cycling network centrality measures'. Together they form a unique fingerprint.
  • University of Essex

    Francesca Arrigo (Visiting researcher)

    19 Nov 201823 Nov 2018

    Activity: Visiting an external institution typesVisiting an external academic institution

Cite this