Unknown

Dataset Information

0

Beyond non-backtracking: non-cycling network centrality measures.


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.

SUBMITTER: Arrigo F 

PROVIDER: S-EPMC7125983 | biostudies-literature | 2020 Mar

REPOSITORIES: biostudies-literature

altmetric image

Publications

Beyond non-backtracking: non-cycling network centrality measures.

Arrigo Francesca F   Higham Desmond J DJ   Noferini Vanni V  

Proceedings. Mathematical, physical, and engineering sciences 20200311 2235


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,  ...[more]

Similar Datasets

| S-EPMC7286920 | biostudies-literature
| S-EPMC7728761 | biostudies-literature
| S-EPMC5967884 | biostudies-literature
| S-EPMC10137616 | biostudies-literature
| S-EPMC10159362 | biostudies-literature
| S-EPMC3847089 | biostudies-literature
| S-EPMC8442596 | biostudies-literature
| S-EPMC7012663 | biostudies-literature
| S-EPMC6079107 | biostudies-literature
| S-EPMC5643020 | biostudies-literature