mathematics//graph theory//diffusion and consensus

What global behavior comes from reducing local differences. The dynamics \(\dot x=-Lx\) makes each node move toward the values of its neighbors,

What global behavior comes from reducing local differences. The dynamics x˙=−Lx\dot x=-Lxx˙=−Lx makes each node move toward the values of its neighbors,

x˙i=∑jwij(xj−xi).\dot x_i=\sum_jw_{ij}(x_j-x_i).x˙i​=j∑​wij​(xj​−xi​).

Assume a fixed undirected network, non-negative weights and a time scale that makes the equation dimensionally valid. In physics it can describe diffusion; in distributed algorithms, consensus. The shared equation does not erase the difference between the two readings.

What is conserved and where it ends. Since 1TL=0\mathbf1^{\mathsf T}L=01TL=0, the sum of the states stays constant. If the network is connected, x(t)→xˉ1x(t)\to\bar x\mathbf1x(t)→xˉ1 with xˉ=1n∑ixi(0)\bar x=\frac1n\sum_i x_i(0)xˉ=n1​∑i​xi​(0). A disconnected network reaches one value per component. With unequal capacities, Mx˙=−LxM\dot x=-LxMx˙=−Lx conserves the weighted sum and reaches the weighted average of nodal capacity. Inputs and boundaries matter too: an imposed temperature or a leak can remove the conservation and change the equilibrium.

Consensus does not mean attraction to any chosen constant. Every constant state is an equilibrium. A perturbation that changes the mean leads to another constant equilibrium: the consensus family attracts the disagreements, while the common component does not decay. In the subspace of fixed mean there is a single compatible equilibrium and the disagreement modes vanish exponentially. That is the precise sense of "stable" in a conservative network (equilibrium and stability).

Directed networks. A Laplacian with zero row sums satisfies L1=0L\mathbf1=0L1=0 even if it is not symmetric. In a strongly connected directed network with non-negative weights the continuous consensus can be

x(t)⟶1 ωTx(0),ωTL=0,ωT1=1.x(t)\longrightarrow\mathbf1\,\omega^{\mathsf T}x(0),\qquad \omega^{\mathsf T}L=0,\quad \omega^{\mathsf T}\mathbf1=1.x(t)⟶1ωTx(0),ωTL=0,ωT1=1.

The final weighting depends on the left eigenvector and need not be the arithmetic mean. For conservative transport of column quantities the corresponding operator usually acts transposed, as in a Markov chain. A check valve is not represented automatically by constant asymmetric weights: qij=kmax⁡(hi−hj,0)q_{ij}=k\max(h_i-h_j,0)qij​=kmax(hi​−hj​,0) is a piecewise nonlinear law.

The graph Laplacian expresses the local action; the spectral gap gives the collective speed; the Lyapunov function verifies the loss of disagreement. Consensus of node values is not the same object as a stationary distribution of occupation.