A second-order random walk on a graph or network is a random walk where transition probabilities depend not only on the present node but also on the previous one. A notable example is the non-backtracking random walk, where the walker is not allowed to revisit a node in one step. Second-order random walks can model physical diffusion phenomena in a more realistic way than traditional random walks and have been very successfully used in various network mining and machine learning settings. However, numerous questions are still open for this type of stochastic processes. In this work we extend well-known results concerning mean hitting and return times of standard random walks to the second-order case. In particular, we provide simple formulas that allow us to compute these numbers by solving suitable systems of linear equations. Moreover, by introducing the "pullback" first-order stochastic process of a second-order random walk, we provide second-order versions of the renowned Kac's and random target lemmas.
翻译:图形或网络上的第二顺序随机行走是一种随机行走,过渡概率不仅取决于当前节点,而且取决于上一个节点。一个显著的例子就是非后跟踪随机行走,不容许行走者一步地重访一个节点。第二顺序随机行走可以比传统的随机行走更现实的方式模拟物理扩散现象,并在各种网络采矿和机器学习环境中非常成功地使用。然而,对于这种类型的随机过程,仍然有许多问题有待解决。在这项工作中,我们将关于标准随机行走的平均打击和返回时间的众所周知的结果推广到第二阶点的情况。特别是,我们提供了简单的公式,使我们能够通过解决合适的线性方程系统来计算这些数字。此外,通过引入第二顺序随机行走的“回击”第一阶随机路,我们提供了著名的Kac和随机目标lemmas的第二顺序版本。