Beyond non-backtracking: non-cycling network centrality measures

Francesca Arrigo, Desmond J. Higham, Vanni Noferini*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

38 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
DOIs
Publication statusPublished - 25 Mar 2020
MoE publication typeA1 Journal article-refereed

Keywords

  • centrality index
  • deformed graph Laplacian
  • Hashimoto matrix
  • complex network
  • matrix polynomial
  • generating function
  • ZETA-FUNCTIONS
  • COMMUNICABILITY
  • GRAPHS

Cite this