Supplementary Summary from Beyond non-backtracking: non-cycling network centrality measures

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.

图上的行走问题在诸多领域均有研究，涵盖图论、随机分析、理论计算机科学乃至物理学。在诸多场景下，研究者往往关注无回溯行走（non-backtracking walks）——即不会立即回溯至前一位置的行走路径。在网络科学语境中，针对传统基于行走的节点中心性指标施加无回溯约束，已被证实可带来切实益处。本文借助桥本矩阵（Hashimoto matrix）构造，对这类无回溯中心性指标进行表征、推广与研究。随后，我们提出一种递归扩展方法，可系统性地移除三角形、四边形，乃至任意给定长度以内的所有环。通过刻画对应矩阵幂级数的谱半径，我们探究了经典基于行走的中心性指标的极限行为普适性结论，如何延伸至这些无环行走场景。此外，我们还证明了这种新型递归构造可生成可应用于大规模网络的实用中心性指标。