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

preprint2012arXivOpen access

Abstract

For λ>0λ>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 λ1+λ\fracλ{1+λ}, otherwise continued with probability 11+λ\frac{1}{1+λ}. We use the Aldous-Broder algorithm (\cite{aldous, broder}) of generating a random spanning tree and the Matrix-tree theorem to relate the values of the characteristic polynomial of the Laplacian at ±λ\pm λ and the stationary measures of the sets of nodes visited by ii independent λλ-damped random walks for i∈Ni \in \N. As a corollary, we obtain a new characterization of the non-zero eigenvalues of the Weighted Graph Laplacian.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.