Arrigo, Francesca and Grindrod, Peter and Higham, Desmond J and Noferini, Vanni (2018) On the exponential generating function for non-backtracking walks. Linear Algebra and its Applications, 556. pp. 381-399. DOI https://doi.org/10.1016/j.laa.2018.07.010
Arrigo, Francesca and Grindrod, Peter and Higham, Desmond J and Noferini, Vanni (2018) On the exponential generating function for non-backtracking walks. Linear Algebra and its Applications, 556. pp. 381-399. DOI https://doi.org/10.1016/j.laa.2018.07.010
Arrigo, Francesca and Grindrod, Peter and Higham, Desmond J and Noferini, Vanni (2018) On the exponential generating function for non-backtracking walks. Linear Algebra and its Applications, 556. pp. 381-399. DOI https://doi.org/10.1016/j.laa.2018.07.010
Abstract
We derive an explicit formula for the exponential generating function associated with non-backtracking walks around a graph. We study both undirected and directed graphs. Our results allow us to derive computable expressions for non-backtracking versions of network centrality measures based on the matrix exponential. We find that eliminating backtracking walks in this context does not significantly increase the computational expense. We show how the new measures may be interpreted in terms of standard exponential centrality computation on a certain multilayer network. Insights from this block matrix interpretation also allow us to characterize centrality measures arising from general matrix functions. Rigorous analysis on the star graph illustrates the effect of non-backtracking and shows that localization can be eliminated when we restrict to non-backtracking walks. We also investigate the localization issue on synthetic networks.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Centrality; Matrix function; Localization; Network science |
Subjects: | Q Science > QA Mathematics |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Mathematics, Statistics and Actuarial Science, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 30 Jul 2018 09:49 |
Last Modified: | 16 May 2024 19:25 |
URI: | http://repository.essex.ac.uk/id/eprint/21908 |
Available files
Filename: 1s20S0024379518303288main.pdf
Licence: Creative Commons: Attribution 3.0