Random walk graph diffusion

First -- Dr. Cosma Shalizi.
This is from his 2009 lecture on Diffusion Maps:

"This is saying that the substance will move away from regions of high concentration and towards ones of low concentration, until it's evenly distributed everywhere. On the one hand, it's almost Biblical; on the other hand, it's the mathematical expression of what we mean when in ordinary language we say it oozes." -- Isaiah 40:4, "Every valley shall be exalted, and every mountain and hill shall be laid low"

"I confess I chose this picture because it makes me seem older and more important than I really am."

A quick overview

A random walk is a markov process. The probability of a random walker visiting node B given it's currently visiting node A. If we fix the probabilities, the process will settle to an equilibrium (the number of random walkers @ any given node will stay constant). This is the essence of the original pagerank algo (ergodicity). The key point is we can start anywhere and settle to an equilibrium.

Some more resources

Data reduction using spectral methods

Diffusion maps, spectral clustering and reaction coordinates of dynamical systems

Some other related things

check out 'network thermodynamics'