Projects per year
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 language | English |
---|---|
Article number | 20190653 |
Number of pages | 28 |
Journal | Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences |
Volume | 476 |
Issue number | 2235 |
Early online date | 11 Mar 2020 |
DOIs | |
Publication status | Published - 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.Profiles
Projects
- 2 Finished
-
Don't look back -- non-backtracking walks in complex networks (ECF)
Arrigo, F. (Principal Investigator)
1/05/19 → 30/04/22
Project: Research Fellowship
-
Data Analytics for Future Cities
Higham, D. (Principal Investigator)
EPSRC (Engineering and Physical Sciences Research Council)
1/01/15 → 31/12/19
Project: Research Fellowship
Activities
- 1 Visiting an external academic institution
-
University of Essex
Arrigo, F. (Visiting researcher)
19 Nov 2018 → 23 Nov 2018Activity: Visiting an external institution types › Visiting an external academic institution