mathematics//graph theory//diffusion and consensus

Diffusion and consensus are the two readings of one network dynamics in which every node moves toward the values of its neighbors, so that local differences shrink until the whole network shares one value, and they describe both physical spreading and distributed agreement. It is heat evening out through a plate (the diffusion equation written on the nodes of a mesh), water levels settling across connected tanks, and a swarm of drones or a network of sensors agreeing on one value by talking only to their neighbours, with no central computer. The dynamics \(\dot x=-Lx\) makes each node move toward the values of its neighbors,

Diffusion and consensus are the two readings of one network dynamics in which every node moves toward the values of its neighbors, so that local differences shrink until the whole network shares one value, and they describe both physical spreading and distributed agreement. It is heat evening out through a plate (the diffusion equation written on the nodes of a mesh), water levels settling across connected tanks, and a swarm of drones or a network of sensors agreeing on one value by talking only to their neighbours, with no central computer. 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 (an averaging flow that converges by itself, unrelated to blockchain consensus and to the distributed consensus of replicated servers, which agree exactly on one discrete history by vote). The shared equation does not erase the difference between the two readings; how a fleet runs it on real radios is the consensus protocol.

λ2, the slowest decay0.354 final value, the average0.50 One side starts hot and heat flows along the edges by dx/dt = −Lx. t = 0.0: spread 1.00; t = 1.4: spread 0.65; t = 4.2: spread 0.24; t = 8.5: spread 0.05. Each mode fades as e^(−λt): the fast ones vanish first, the slow one, one group against the other, lingers, and the constant mode, the average, never decays.

Tap a node to heat it and let it spread. On the right each mode fades at its own rate: the average never moves, and the slow mode that separates the two communities is the last disagreement to die.

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): drones agreeing on a meeting point reach the mean of where they started, and nobody computed it. Every other Laplacian mode decays as e−λite^{-\lambda_i t}e−λi​t, so the time to agree scales as 1/λ21/\lambda_21/λ2​. 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).

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.

?And if the connections have a direction?

Then the consensus is not the plain average. A Laplacian with zero row sums satisfies L1=0L\mathbf1=0L1=0 even if it is not symmetric, and 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. 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.