Supplementary Summary from Beyond non-backtracking: non-cycling network centrality measures

Francesca Arrigo, Desmond J. Higham, Vanni NoferiniFigshare 2020 · DOI · OpenAlex

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.
BibTeX
@inproceedings{arrigo2020supplementary,
  author = {Francesca Arrigo and Desmond J. Higham and Vanni Noferini and Desmond Higham},
  title = {{Supplementary Summary from Beyond non-backtracking: non-cycling network centrality measures}},
  booktitle = {Figshare},
  year = {2020},
  doi = {10.6084/m9.figshare.11953740},
}

Loading related content...

Figure