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

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

2005-06-22

arxiv.org/abs/math/0506460v2

Mathematics

Probability

This paper does not contain essentially new results

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Damped random walks and the characteristic polynomial of the weighted Laplacian on a graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Damped random walks and the characteristic polynomial of the weighted Laplacian on a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Damped random walks and the characteristic polynomial of the weighted Laplacian on a graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-480735