## 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 |

DOIs | |

Publication status | Published - 25 Mar 2020 |

MoE publication type | A1 Journal article-refereed |

## Keywords

- centrality index
- deformed graph Laplacian
- Hashimoto matrix
- complex network
- matrix polynomial
- generating function
- ZETA-FUNCTIONS
- COMMUNICABILITY
- GRAPHS