Damped random walks and the characteristic polynomial of the weighted Laplacian on a graph

2005/06/22 by Desai, Madhav, Narayanan, Hariharan
#60C05 #68R10 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.math/0506460

Abstract

For λ>0, we define a λ-damped random walk to be a random walk that is started from a random vertex of a graph and stopped at each step with probability \fracλ1+λ, otherwise continued with probability (1)/(1+λ). We use the Aldous-Broder algorithm (\citealdous, broder) of generating a random spanning tree and the Matrix-tree theorem to relate the values of the characteristic polynomial of the Laplacian at ± λ and the stationary measures of the sets of nodes visited by i independent λ-damped random walks for i ∈ \N. As a corollary, we obtain a new characterization of the non-zero eigenvalues of the Weighted Graph Laplacian.

Related

• Eigenfunctions of the Edge-Based Laplacian on a Graph
• Random walks and Laplacians on hypergraphs: When do they match?
• A Characteristic Polynomial for The Transition Probability Matrix of A Correlated Random Walk on A Graph
• Some relations between the spectra of simple and non-backtracking random walks
• Generating Functions of Random Walks on Graphs