 Diffusion on a graph

The continuous-time diffusion model on a finite undirected graph uses the Graph Laplacian in the ordinary differential equationAcross 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: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 isMore 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,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.