Beyond non-backtracking: non-cycling network centrality measures

Francesca Arrigo, Desmond J. Higham, Vanni NoferiniProceedings of the Royal Society A Mathematical Physical and Engineering Sciences 2020 · DOI

TL;DR

This paper extends the concept of "non-backtracking" walks in networks to "non-cycling" walks, which avoid all cycles up to a specified length. By developing a novel recursive construction based on the Hashimoto matrix, the authors introduce new centrality measures that offer improved network analysis, particularly for large-scale, complex networks.

What Problem Does This Paper Address?

Centrality measures are crucial for understanding the importance of nodes in networks. Traditional methods often rely on counting walks, but these can be overly influenced by short, repetitive paths (backtracking or cycles). Non-backtracking walks, which disallow immediate reversals, have shown promise in improving centrality measures. However, existing methods still struggle with the influence of longer cycles. This paper addresses the challenge of developing network centrality measures that systematically eliminate the impact of all cycles up to a given length, leading to more robust and insightful analyses of complex networks.

Methods

The authors build upon the Hashimoto matrix construction, which is designed to count non-backtracking walks. They generalize this by introducing a recursive method to construct matrices that count "non-k-cycling" walks – walks that do not backtrack and avoid cycles of length up to $k$. This involves defining "non-k-cycling matrices" ($P_k$) and leveraging source and target matrices to project from the edge space to the node space. The paper also explores the spectral properties of these matrices and their associated power series to understand the limiting behavior of the centrality measures.

Datasets

The paper does not explicitly mention training datasets. For evaluation and illustration, the authors use:

  • Small-world networks: Generated using the smallw function from the CONTEST toolbox for MATLAB.
  • Preferential attachment networks: Generated using a preferential attachment model.
  • Real-world networks: Specifically, the largest connected components of the CA-HEPTH and ERDOS02 collaboration networks.

Key Insights and Ideas

  • Generalizing Non-Backtracking: The core idea is to move beyond simply avoiding immediate reversals to actively excluding all cycles up to a certain length, offering a more refined way to analyze network structure.
  • Recursive Construction of $P_k$: The development of a recursive method to build matrices that count non-k-cycling walks is a key technical contribution, allowing for systematic removal of cycles.
  • Duality and Projection: The use of source and target matrices to move between edge and node spaces provides a powerful framework for relating walk counts to node-based centralities.
  • Universality and Limiting Behavior: The study of how these non-cycling centrality measures behave in the limit, particularly as parameters approach certain values, reveals interesting connections to network topology and provides insights into their robustness.
  • Pruning for Efficiency: The concept of "generalized pruning" suggests that network analysis can be made more efficient by removing nodes that do not contribute to longer cycles, simplifying the problem without losing essential information.

Key Results

  • The paper introduces a framework for computing non-k-cycling centrality measures for any analytic function.
  • Theoretical results are presented that characterize the spectra of the associated matrices and the limiting behavior of these centrality measures.
  • The study demonstrates that these new measures can be practically applied to large-scale networks, as evidenced by experiments on real-world network data.
  • The analysis shows that the density of the non-k-cycling matrices ($P_k$) remains low even as network size increases, suggesting computational feasibility.

Limitations and Future Work

  • Computational Complexity: The authors acknowledge that computing the $P_k$ matrices can lead to exponential complexity in the worst case, especially for large $k$. However, they suggest that for sparse real-world networks, this might not be a significant issue.
  • Universality Classes: While the paper explores universality, it notes that for non-k-cycling centrality measures, there might not be a universal eigenvector-based measure, unlike in the non-backtracking case.
  • Future Directions: The authors suggest further research into:
  • Developing spectral results for $P_k$ and their consequences for centrality measure localization.
  • Designing faster linear algebra algorithms that exploit the structure of matrix-based subproblems.
  • Conducting large-scale tests of the new measures on real-world complex networks.

Summary updated

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.
BibTeX
@inproceedings{arrigo2020beyond,
  author = {Francesca Arrigo and Desmond J. Higham and Vanni Noferini},
  title = {{Beyond non-backtracking: non-cycling network centrality measures}},
  booktitle = {Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences},
  year = {2020},
  doi = {10.1098/rspa.2019.0653},
}
Figure