论文标题
回溯量漫步的理论
A Theory for Backtrack-Downweighted Walks
论文作者
论文摘要
在每个回溯步骤都被给定因素降低了重量的情况下，我们为在有向图上进行步行计数的组合制定了一个完整的理论。通过得出相关生成函数的表达式，我们还获得了在这种情况下计算中心度度量的线性系统。特别是，我们表明可以以与标准katz相同的成本计算倒数量的Katz风格网络中心性。研究这种中心度度量在其收敛性半径上的极限也导致了回溯量的特征向量中心性的新表达式，将先前的工作推广到存在有向边缘的情况下。新理论使我们能够结合标准和非背带案例的优势，在考虑类似树状结构的同时避免本地化。我们说明了合成网络和真实网络对回溯量量的中心度度量的行为。
We develop a complete theory for the combinatorics of walk-counting on a directed graph in the case where each backtracking step is downweighted by a given factor. By deriving expressions for the associated generating functions, we also obtain linear systems for computing centrality measures in this setting. In particular, we show that backtrack-downweighted Katz-style network centrality can be computed at the same cost as standard Katz. Studying the limit of this centrality measure at its radius of convergence also leads to a new expression for backtrack-downweighted eigenvector centrality that generalizes previous work to the case where directed edges are present. The new theory allows us to combine advantages of standard and nonbacktracking cases, avoiding localization while accounting for tree-like structures. We illustrate the behaviour of the backtrack-downweighted centrality measure on both synthetic and real networks.
