mathematics//graph theory//graph Laplacian
The graph Laplacian is the matrix through which a network of connections turns differences between nodes into a local balance. It is behind heat spreading through a mesh, water levels evening out between connected tanks, a sensor network agreeing on one reading, and the algorithms that cut a graph into communities or smooth a signal over it. For an undirected network with non-negative weights,
The graph Laplacian is the matrix through which a network of connections turns differences between nodes into a local balance. It is behind heat spreading through a mesh, water levels evening out between connected tanks, a sensor network agreeing on one reading, and the algorithms that cut a graph into communities or smooth a signal over it. For an undirected network with non-negative weights,
L=D−W,(Lx)i=∑jwij(xi−xj).\cc{L}=\cb{D}-\ca{W},\qquad (\cc{L}x)_i=\sum_j\ca{w_{ij}}(x_i-x_j).L=D−W,(Lx)i=j∑wij(xi−xj).
The Laplacian in copper, the degrees in blue, the weights in green. L\cc{L}L is the unnormalized Laplacian. xxx assigns a value to each node; Lx\cc{L}xLx sums the weighted differences of that node with respect to its neighbors. It is not yet a velocity: it becomes one, with the right sign and units, when inserted into a dynamic equation.
graph8 nodes, 7 edges λ20.152 λ83.848 Mode 2 of the Laplacian: each node displaced by its value in the eigenvector. Low modes are smooth, high modes alternate between neighbours and vibrate faster, with ω growing as √λ.
The eigenvectors of L\cc{L}L are the network's vibration modes, the discrete cousins of a string's harmonics, and they serve as its Fourier basis (on a ring they are exactly sines and cosines). Step through them: low modes are smooth over the connections, high modes flip sign between neighbours, and the eigenvalue grows with the wiggle.
The Laplacian turns a graph into eigenvalues, and the same matrix appears wherever a network carries something.
Zero counts the pieces, λ2\lambda_2λ2 measures connectivity and the speed of agreement, the slow modes find the groups. Heat on a mesh (diffusion equation), a fleet agreeing on a meeting point (consensus protocol), a random walk on the nodes, spectral clustering and the layers of a GNN are this one matrix read differently.
A pipe law turns the Laplacian into a nodal balance. If a pipe obeys qij=kij(hi−hj)q_{ij}=k_{ij}(h_i-h_j)qij=kij(hi−hj), (Lh)i(\cc{L}h)_i(Lh)i is the net outflow from tank iii. Zero net balance at one node does not mean every flow is zero, since water can enter through one pipe and leave through another; only in a whole closed, passive, connected network with no sources does Lh=0\cc{L}h=0Lh=0 imply equal levels and no flow.
The constant mode counts the connected components. Since L1=0\cc{L}\mathbf1=0L1=0, the constant vector is an eigenvector of eigenvalue zero, with one independent constant mode per connected component; the multiplicity of the zero eigenvalue counts them.
The quadratic form measures disagreement,
xTLx=12∑i,jwij(xi−xj)2≥0.x^{\mathsf T}\cc{L}x=\frac12\sum_{i,j}\ca{w_{ij}}(x_i-x_j)^2\ge0.xTLx=21i,j∑wij(xi−xj)2≥0.
The factor 1/21/21/2 avoids counting each edge twice in the ordered sum. This identity (the Dirichlet energy of xxx) explains why L\cc{L}L is positive semidefinite and connects smoothness over the graph with its eigenvalues.
The ends of the spectrum are read directly. λ2\lambda_2λ2 is positive exactly when the graph is connected (spectral gap), and the signs of its eigenvector, the Fiedler vector, mark where the graph would cut. The largest eigenvalue λN\lambda_NλN bounds the step of discrete consensus (ε<2/λN\varepsilon<2/\lambda_Nε<2/λN) and the delay it tolerates.
nodal capacity turns the balance into rates; diffusion and consensus studies its evolution; the normalized Laplacian changes the weighting by degree.
?Why does it share a name with the Laplacian of calculus?
Because on a mesh it is the same operator, discretized. On a one-dimensional mesh with spacing Δs\Delta sΔs, the interior stencil is
(Lx)iΔs2=2xi−xi−1−xi+1Δs2≈−∂2x∂s2.\frac{(\cc{L}x)_i}{\Delta s^2}=\frac{2x_i-x_{i-1}-x_{i+1}}{\Delta s^2}\approx-\frac{\partial^2x}{\partial s^2}.Δs2(Lx)i=Δs22xi−xi−1−xi+1≈−∂s2∂2x.
With the positive convention L=D−W\cc{L}=\cb{D}-\ca{W}L=D−W, it is −L-\cc{L}−L that matches the usual sign of Δ=∇⋅∇\Delta=\nabla\cdot\nablaΔ=∇⋅∇ in the diffusion equation. The name does not erase that sign difference; see gradient, divergence and curl.