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

Research paper by **Madhav Desai, Hariharan Narayanan**

Indexed on: **15 Jan '12**Published on: **15 Jan '12**Published in: **Mathematics - Probability**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

For $\lambda>0$, we define a $\lambda$-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{\lambda}{1+\lambda}$, otherwise continued with probability
$\frac{1}{1+\lambda}$. 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
\lambda$ and the stationary measures of the sets of nodes visited by $i$
independent $\lambda$-damped random walks for $i \in \N$. As a corollary, we
obtain a new characterization of the non-zero eigenvalues of the Weighted Graph
Laplacian.