Non-backtracking centrality measures and beyond

Thumbnail Image

Files

isbn9789526424644.pdf (481 KB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Doctoral thesis (article-based) | Defence date: 2025-04-11
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2025

Department

Matematiikan ja systeemianalyysin laitos
Department of Mathematics and Systems Analysis

Major/Subject

Mcode

Degree programme

Language

en

Pages

47 + app. 97

Series

Aalto University publication series Doctoral Theses, 63/2025

Abstract

Centrality measures are non-negative valued functions, typically defined on the nodes of a network, that assign to each node a value indicative of its importance within the network. There exists a multitude of centrality measures which is reflective of the fact that different network features can be more or less important in different applications. Centrality measures based on non-backtracking walks have been shown to possess various benefits over other more simplistic walk-based centrality measures, such as not exhibiting localization [32] of centrality in network hubs. However, the combinatorics of computing nonbacktracking centralities can be extremely complicated, which has hitherto been an obstacle to their application to the more general class of networks with weighted edges that are possibly timeevolving. The subject of the present dissertation is the expansion of the class of networks to which nonbacktracking centrality measures can be applied. In particular, we examine various obstacles that prohibit the direct application of existing non-backtracking formulae. These are the presence of non-uniformly weighted edges, the possibility of a time-dependence to a network's structure and the weighting of edges. Additionally, in the case of a dense network with an abundance of edges, existing formulae of Katz and non-backtracking Katz can become intractable. Publications I and II address the first three obstacles by introducing a multilayer graph approach as well as a node-level formula for weighted, static graphs. The final obstacle forms the main subject of Publications III & IV, wherein we present alternative formulations of both Katz and non-backtracking Katz centralities. This investigation was motivated by a particular financial experiment involving weighted, time-evolving networks with high edge densities. The new formulations are then tested by means of computational experiments on both real and randomly generated networks, and are thereby experimentally shown to be more computationally efficient.

Description

Supervising professor

Noferini, Vanni, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland

Thesis advisor

Noferini, Vanni, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland

Keywords

centrality measures, nonbacktracking walk, complex network, matrix function, line graph

Other note

Parts

  • [Publication 1]: Francesca Arrigo, Desmond J. Higham, Vanni Noferini, and Ryan Wood. Dynamic Katz and Related Network Measures. Linear Algebra and its Applications, Volume 655, Pages 159–185, December 2022.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202212146882
    DOI: 10.1016/j.laa.2022.08.022 View at publisher
  • [Publication 2]: Francesca Arrigo, Desmond J. Higham, Vanni Noferini, and Ryan Wood. Weighted Enumeration of Nonbacktracking Walks on Weighted Graphs. SIAM Journal on Matrix Analysis and Applications, Volume 45, Pages 397–418, March 2024.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202404113027
    DOI: 10.1137/23M155219X View at publisher
  • [Publication 3]: Vanni Noferini and Ryan Wood. Efficient computation of Katz centrality for very dense networks via negative parameter Katz. Journal of Complex Networks, Volume 12, Issue 5, October 2024.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202410096656
    DOI: 10.1093/comnet/cnae036 View at publisher
  • [Publication 4]: Vanni Noferini, Spyridon Vrontos and Ryan Wood. Efficient Computation of f-centralities and Nonbacktracking Centrality for Temporal Networks. Submitted to SIAM Journal on Applied Mathematics, October 2024.

Citation

Permanent link to this item

https://urn.fi/URN:ISBN:978-952-64-2464-4

Collections

[diss] Perustieteiden korkeakoulu / SCI