Beyond non-backtracking : non-cycling network centrality measures

Arrigo, Francesca and Higham, Desmond J. and Noferini, Vanni (2020) Beyond non-backtracking : non-cycling network centrality measures. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 476 (2235). 20190653. ISSN 1471-2962

[thumbnail of Arrigo-etal-PRS-MPES-2020-non-cycling-network-centrality-measures]
Preview
 Text (Arrigo-etal-PRS-MPES-2020-non-cycling-network-centrality-measures)
Arrigo_etal_PRS_MPES_2020_non_cycling_network_centrality_measures.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (980kB)| Preview

    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.

    ORCID iDs

    Arrigo, Francesca ORCID logoORCID: https://orcid.org/0000-0001-5473-7284, Higham, Desmond J. and Noferini, Vanni;
    • Item type:Article
      ID code:71648
      Dates:
      Date
      Event
      25 March 2020
      Published
      11 March 2020
      Published Online
      12 February 2020
      Accepted
      Keywords:centrality index, deformed graph Laplacian, Hashimoto matrix, complex network, matrix polynomial, generating function, Mathematics, Mathematics(all)
      Subjects:Science > Mathematics
      Department:Faculty of Science > Mathematics and Statistics
      Depositing user: Pure Administrator
      Date deposited:03 Mar 2020 15:30
      Last modified:23 Sep 2021 07:39
      URI:https://strathprints.strath.ac.uk/id/eprint/71648
    CORE (COnnecting REpositories)