Beyond non-backtracking: non-cycling network centrality measures.
Beyond non-backtracking: non-cycling network centrality measures.
复制标题
超越非回溯：非循环网络中心性措施。
DOI：
10.1098/rspa.2019.0653
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Arrigo F
中科院分区：
文献类型：
--
作者：
Arrigo F
图的遍历在很多领域都有研究，从图论和随机分析到理论计算机科学和物理学。在许多情况下，关注非回溯行走是有意义的;那些不会立即重新访问其先前位置的行走。在网络科学的背景下，对传统的基于步行的节点中心性措施施加非回溯约束，可以提供切实的好处。在这里，我们使用桥本矩阵的结构来刻画，推广和研究这样的非回溯中心性措施。然后，我们设计了一个递归扩展，系统地删除三角形，正方形，一般来说，所有周期到给定的长度。通过表征适当的矩阵幂级数的谱半径，我们探讨了经典的步行为基础的中心性措施的限制行为的普遍性结果如何扩展到这些非循环的情况下。我们还证明了新的递归结构产生了实际的中心性措施，可以应用于大规模的网络。
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.