Beyond non-backtracking: non-cycling network centrality measures
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Major/Subject
Mcode
Degree programme
Language
en
Pages
28
Series
Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, Volume 476, issue 2235
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.Description
Other note
Citation
Arrigo, F, Higham, D J & Noferini, V 2020, 'Beyond non-backtracking : non-cycling network centrality measures', Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 476, no. 2235, 20190653. https://doi.org/10.1098/rspa.2019.0653