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 nonbacktracking walks; those that do not immediately revisit their previous location. In the network science context,imposing a nonbacktracking constraint on traditional walkbased node centrality measures is known to offer tangible benefits. Here, we use the Hashimoto matrix construction to characterize, generalize and study such nonbacktracking 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 walkbased centrality measures extend to these noncycling 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 nonbacktracking: noncycling network centrality measures'. Together they form a unique fingerprint.Profiles
Projects
 2 Finished

Don't look back  nonbacktracking walks in complex networks (ECF)
1/05/19 → 30/04/22
Project: Research Fellowship

Data Analytics for Future Cities
Higham, D.
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
Francesca Arrigo (Visiting researcher)
19 Nov 2018 → 23 Nov 2018Activity: Visiting an external institution types › Visiting an external academic institution