Significance of the random walk normalized graph Laplacian

Question

I've been studying the graph Laplacian and random walks on graphs. The Wikipedia article on the Graph Laplacian defines the random walk normalized Laplacian in detail. But, unfortunately, it does not motivate this definition.

My question is simply: what is the significance of this random walk normalized Laplacian?

Thanks in advance, Joshua

Answer 1

If $A$ is the adjacency matrix of a graph, and $D$ is the diagonal matrix of vertex degrees, then $P = D^{-1}A$ is the transition matrix for the random walk on the graph. If row vector $x(t)$ is the probability distribution of the random walk at time $t$, then $x(t+1) = x(t) P$. This means that if you're thinking about the random walk on your graph, you should already be looking at $P$ rather than $A$.

The random walk normalized Laplacian is $L = I - P$. As a result:

• $L$ shares the eigenvectors of $P$, and if $\lambda$ is an eigenvalue of $P$, then $1-\lambda$ is an eigenvalue of $L$. In that sense, we lose nothing by studying $L$ instead of $P$.
• Since the eigenvalues of $P$ are all at most $1$, the eigenvalues of $L$ are all at least $0$: $L$ is positive semidefinite. (Well, sort of - it's not symmetric, which is what fancier versions of the Laplacian try to fix.) This is a slightly more convenient property.
• The condition for a probability distribution $x$ on the vertices to be a stationary distribution of the random walk is that $x = xP$. We can now rewrite this as $xL = 0$.