2021/05/30 by Dario Fasino, Fasino, Dario, Arianna Tonetto +3 · 1 citation
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2105.14438
openalex publication_date 2021/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.