mathematics//graph theory//graph Laplacian

How a network of connections turns differences between nodes into a local balance. For an undirected network with non-negative weights,

How a network of connections turns differences between nodes into a local balance. For an undirected network with non-negative weights,

L=D−W,(Lx)i=∑jwij(xi−xj).L=D-W,\qquad (Lx)_i=\sum_jw_{ij}(x_i-x_j).L=D−W,(Lx)i​=j∑​wij​(xi​−xj​).

LLL is the unnormalized Laplacian. xxx assigns a value to each node; LxLxLx 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.

From a pipe to a nodal balance. If a pipe obeys qij=kij(hi−hj)q_{ij}=k_{ij}(h_i-h_j)qij​=kij​(hi​−hj​), the component (Lh)i(Lh)_i(Lh)i​ is the net outflow from tank iii, so −Lh-Lh−Lh is the net inflow. If (Lh)i=0(Lh)_i=0(Lh)i​=0 at one node considered alone, water may enter through some pipes and leave through others: zero net balance does not mean every flow is zero. For a whole closed, passive, connected network with no sources, Lh=0Lh=0Lh=0 does imply equal levels and no flow on every edge. With sources, pumps or imposed boundaries a steady regime with circulation can exist.

The constant mode and the components. L1=0L\mathbf1=0L1=0: the constant vector is an eigenvector of eigenvalue zero. If the undirected graph has several connected components, there is one independent constant mode per 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}Lx=\frac12\sum_{i,j}w_{ij}(x_i-x_j)^2\ge0.xTLx=21​i,j∑​wij​(xi​−xj​)2≥0.

The factor 1/21/21/2 avoids counting each edge twice in the ordered sum; summing once per undirected edge drops it. This identity explains why LLL is positive semidefinite and connects smoothness over the graph with its eigenvalues.

Why it shares a name with the continuous Laplacian. 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{(Lx)_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−WL=D-WL=D−W, it is −L-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.

nodal capacity turns the balance into rates; diffusion and consensus studies its evolution; the normalized Laplacian changes the weighting by degree.