Beyond non-backtracking: non-cycling network centrality measures

Francesca Arrigo, Desmond J. Higham, Vanni Noferini

Research output: Contribution to journalArticle

13 Downloads (Pure)

Abstract

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
Volume476
Issue number2235
Early online date11 Mar 2020
DOIs
Publication statusPublished - 25 Mar 2020

Keywords

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

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

  • Cite this