Continuous-time random walks on graphs are in some sense discrete analogue of diffusions on a Riemannian manifold (of course, the reverse can be argued, but I think that diffusions play a more central role in modern probability theory).  Of course, the most important diffusion is Brownian motion, i.e., the Markov process associated with the Laplace-Beltrami operator.  From my perspective, the natural analogue of Brownian motion is the operator $\mathcal{L}_V$ given by (we use unweighted graphs for simplicity)

\begin{equation*}
(\mathcal{L}_Vf)(x) := \sum_{y\sim x} (f(y)-f(x)).
\end{equation*}

A more 'common' choice might be the rate-1 continuous time random walk with generator $\mathcal{L}_C$ given by

\begin{equation*}
(\mathcal{L}_Cf)(x) := \frac{1}{\deg(x)}\sum_{y\sim x} (f(y)-f(x)).
\end{equation*}

However, this choice of generator has several 'bad' properties if you want to view it as an analogue of Brownian motion -- for example, the generator is always bounded on $L^2(\deg)$, it cannot have discrete spectrum, and the associated random walk cannot explode; in contrast, the operator $\mathcal{L}_V$ may be unbounded, and discrete spectrum and explosiveness are possible.

Once you have this discrete (space) analogue of Brownian motion on a Riemannian manifold, a natural question is to ask what the discrete analogue of the Riemannian metric should be for this process, since among other things, the Riemannian metric governs (in some sense) the heat flow on the manifold (see e.g. [here][1]).  It is not too hard to find examples that show that the graph metric is a bad analogue.  A reasonable analogue has been formulated here, see e.g. [here][2] and [here][3].


  [1]: http://www.math.uni-bielefeld.de/~grigor/super.pdf
  [2]: http://arxiv.org/abs/1012.5050
  [3]: http://arxiv.org/abs/1201.5908