= Diffusion on a graph
{title2=$\dot x=-Lx$}
The continuous-time <diffusion> model on a finite <undirected graph> uses the <Graph Laplacian> in the <ordinary differential equation>
$$
\dot x=-Lx,\qquad \dot x_i=\sum_{j:\{i,j\}\in E}(x_j-x_i).
$$
Across each <edge>, the higher value sends an amount proportional to the difference to the lower value. The two contributions cancel in the sum over <vertices>, giving <conservation of mass>:
$$
\frac{d}{dt}\sum_i x_i(t)=-\mathbf1^TLx(t)=0.
$$
If the entries represent masses, start with nonnegative entries; signed entries can instead describe deviations from a common level. For the three-<vertex> <path graph>, the initial <vector> $x(0)=(1,0,-1)^T$ is an <eigenvector> with <eigenvalue> one, so the exact solution is
$$
x(t)=e^{-t}(1,0,-1)^T.
$$
More generally, an <eigenvector> with <eigenvalue> $\lambda$ decays by $e^{-\lambda t}$. The <spectral theorem for real symmetric matrices> supplies an <orthonormal basis> of these <eigenvectors>, and the <kernel of a graph Laplacian> identifies the surviving terms. On a nonempty <connected graph>,
$$
\lim_{t\to\infty}x(t)=\bar x\mathbf1,\qquad \bar x=\frac1{|V|}\sum_i x_i(0).
$$
The limiting value is the original <arithmetic mean>. On a disconnected <graph>, each <connected component of a graph> converges to its own original <arithmetic mean>. The same <matrix> therefore measures neighbour disagreement, detects disconnected regions and governs relaxation toward agreement.
Back to article page
