4 added 190 characters in body

Continuous-time random walks on graphs are in some sense a 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. It is not too hard to find examples that show that the graph metric is a bad analogue, since among other things, the Riemannian metric governs heat flow (in some sense) the heat flow on the a Riemannian manifold (see e.g. here). It is , but Gaussian heat kernel estimates do not too hard to find examples that show that hold for the random walk associated with $\mathcal{L}_V$ if you take the manifold heat kernel estimates and replace the distance function with the graph metricis a bad analogue. A reasonable analogue has been formulated recently, see e.g. here and here.

3 added 4 characters in body

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). It is not too hard to find examples that show that the graph metric is a bad analogue. A reasonable analogue has been formulated hererecently, see e.g. here and here.

2 fixed latex

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) \mathcal{L}_Vf)(x) := \sum{y\sim x} (f(y)-f(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) \mathcal{L}_Cf)(x) := \frac{1}{\deg(x)}\sum{y\sim x} (f(y)-f(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). 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 and here.