Averaging Dynamics on Graphs
1 The dynamics
\(x_{t+1}(v)=\frac1{\deg v}\sum _{u\sim v}x_t(u)\), and \(\bar x=\sum _v\deg (v)\, x_0(v)/\sum _v\deg (v)\).
\(\sum _v\deg (v)\, x_{t}(v)\) does not depend on \(t\); without isolated nodes, a round never leaves an interval containing all current values.
Double counting over ordered adjacent pairs; an average of values in an interval stays in it.
2 Convergence
\(x_t(v)=\sum _u W_t(v,u)\, x_0(u)\) with \(W_t\) stochastic and \(W_t(v,u){\gt}0\) when a walk of length \(t\) joins \(v\) and \(u\). On a connected graph with an odd closed walk, some length \(L\) joins every pair.
Induction on \(t\); for \(L\), fix the parity with the odd closed walk and pad with back-and-forth steps.
On a connected graph with an odd closed walk, \(x_t(v)\to \bar x\) for every \(v\).
All entries of \(W_L\) are at least some \(\delta {\gt}0\), so \(\max -\min \) contracts by \(1-|V|\delta \) every \(L\) rounds (Doeblin); the common limit is \(\bar x\) by conservation.
On a connected bipartite graph with at least two nodes, the values \(\pm 1\) of a proper 2-colouring change sign at every round, so they converge nowhere.
All neighbours of a node have the other colour.
3 Rate of convergence
\(P=D^{-1}A\) is the transition matrix of the random walk, \(N=D^{-1/2}AD^{-1/2}\) its symmetric version with eigenvalues \(\lambda _1\ge \lambda _2\ge \dots \ge \lambda _n\), \(\lambda =\max \{ |\lambda _2|,|\lambda _n|\} \) (\(0\) if \(n{\lt}2\)), and \(\pi (v)=\deg (v)/2m\) with \(m\) the number of edges.
\(P^t(u,v)=W_t(u,v)\) is the probability that the walk from \(u\) is at \(v\) after \(t\) steps, and \(x_t=P^tx_0\). If every degree is positive, \(P\) and \(N\) have the same characteristic polynomial, so \(\lambda \) is computed from the spectrum of \(P\).
Induction on \(t\); \(P=SNS^{-1}\) with \(S=D^{-1/2}\).
If every degree is positive, \(|P^t(u,v)-\pi (v)|\le \sqrt{\deg (v)/\deg (u)}\, \lambda ^t\) for all nodes \(u,v\) and all \(t\).
\(P^t(u,v)=\sqrt{\deg (v)/\deg (u)}\, N^t(u,v)\) and \(\pi (v)=\sqrt{\deg (v)/\deg (u)}\, s(u)s(v)\) with \(s=\sqrt\pi \) a unit eigenvector of \(N\) for the eigenvalue \(1\). At most one eigenvalue of \(N\) exceeds \(\lambda \) in absolute value, and then it is \(1\) with eigenvector \(s\); so \(N\) contracts \(s^\perp \) by \(\lambda \), and \(N^t(u,v)-s(u)s(v)=\langle Qe_u,N^tQe_v\rangle \) with \(Q=I-ss^\top \) is at most \(\lambda ^t\) by Cauchy–Schwarz.
On a connected graph with an odd closed walk, \(\lambda {\lt}1\).
An eigenvalue \(\mu \) of \(N\) with \(|\mu |=1\) gives a vector \(y\) with \(x_t=\mu ^ty\) for the dynamics started at \(y\); by Theorem 4 \(\mu =-1\) is impossible and \(\mu =1\) forces \(y\) constant, so \(1\) is a simple eigenvalue and all others have absolute value below \(1\).
If every degree is positive, \(|x_t(u)-\sum _v\pi (v)x_0(v)|\le \lambda ^t\sum _v\sqrt{\deg (v)/\deg (u)}\, |x_0(v)|\).
\(x_t(u)-\sum _v\pi (v)x_0(v)=\sum _v(P^t(u,v)-\pi (v))x_0(v)\) and Theorem 8.
4 Sequential averaging
A step on the edge \((i,j)\) multiplies the state by \(W_{ij}=I-\frac12(e_i-e_j)(e_i-e_j)^\top \); a run applies the steps of a list of oriented edges in order. For a stochastic matrix \(P\) (given as a kernel), \(\bar W_P=I-\bar D/2n+(P+P^\top )/2n\) with \(\bar D_{ii}=\sum _j(P_{ij}+P_{ji})\), and \(\bar W=I-L/2m\) with \(L\) the Laplacian.
\(W_{ij}x\) replaces \(x_i\) and \(x_j\) by their average and keeps the other values; \(W_{ij}\) is doubly stochastic and a symmetric projection, \(W_{ij}^\top W_{ij}=W_{ij}\).
Direct computation; \((e_i-e_j)^\top (e_i-e_j)=2\) for \(i\ne j\).
If a uniformly random node \(i\) contacts \(j\) with probability \(P_{ij}\), then \(\mathbb E[W_{ij}]=\bar W_P\); if a uniformly random oriented edge is selected, then \(\mathbb E[W_{ij}]=\bar W\). On a \(d\)-regular graph with \(d{\gt}0\) and \(P=D^{-1}A\) both equal \((1-1/n)I+P/n\).
Entrywise expansion of \(W_{ij}(a,b)=\delta _{ab}-\frac12(\delta _{ia}-\delta _{ja})(\delta _{ib}-\delta _{jb})\); there are \(\deg (a)\) darts out of \(a\) and \(2m=nd\) darts in all.
For a uniformly random oriented edge, \(\mathbb E[W^\top W]=\bar W\) and \(\mathbb E\| Wx\| ^2=x^\top \bar Wx\); after \(t\) independent uniformly random oriented edges, \(\mathbb E[x_t]=\bar W^tx_0\).
\(W^\top W=W\); for the first moment, induction on \(t\) and linearity of expectation.
5 Strong reconstruction
\(G\) is \(d\)-regular on two clusters \(V_1,V_2\) of \(n\) nodes, each node having \(b\) neighbours in the other cluster; \(\chi =\mathbb 1_{V_1}-\mathbb 1_{V_2}\), \(P=A/d\) with eigenvalues \(\lambda _1\ge \lambda _2\ge \dots \), \(\lambda =\max _{i\ge 3}|\lambda _i|\). Node \(v\) is blue at round \(t\) if \(x_t(v)\ge x_{t-1}(v)\); a coloring is a strong reconstruction if no color appears in both clusters. \(T(n,\delta )=\lceil \log (4n^3)/\log (1+\delta )\rceil +1\).
If \(\lambda {\lt}1-2b/d\) and \(x\in \{ \pm 1\} ^{2n}\), then \(|x_t(v)-\alpha _1-\alpha _2(1-2b/d)^t\chi (v)|\le \lambda ^t\sqrt{2n}\) with \(\alpha _1=\langle x,\mathbb 1\rangle /2n\), \(\alpha _2=\langle x,\chi \rangle /2n\).
\(\mathbb 1\) and \(\chi \) are eigenvectors with eigenvalues \(1\) and \(1-2b/d\), both above \(\lambda \); at most two eigenvalues exceed \(\lambda \) in absolute value, so by equality in Bessel’s inequality their eigenvectors lie in \(\operatorname {span}\{ \mathbb 1,\chi \} \), and \(P\) contracts the orthogonal complement of this plane by \(\lambda \).
On a connected clustered graph with \(1-2b/d{\gt}(1+\delta )\lambda \), if \(x\in \{ \pm 1\} ^{2n}\) and \(\langle x,\chi \rangle \ne 0\), then for \(t\ge T(n,\delta )=O(\log n/\delta )\), \(\operatorname {sgn}(x_{t-1}(u)-x_t(u))=\operatorname {sgn}(\langle x,\chi \rangle \chi (u))\).
\(|\langle x,\chi \rangle |\ge 2\) by parity, \(b\ge 1\) by connectivity, \(d{\lt}2n\), and \((1+\delta )^{t-1}\ge 4n^3\), so the main term of Lemma 16 dominates the errors.
For uniform \(x\in \{ \pm 1\} ^{2n}\), \(P(\langle x,\chi \rangle =0)=\binom {2n}{n}/4^n\le 1/\sqrt{\pi n}\).
\(x\mapsto \{ v: x(v)=\chi (v)\} \) maps the zeros bijectively to the \(n\)-subsets; Wallis’ product.
With probability at least \(1-1/\sqrt{\pi n}\), the coloring is a strong reconstruction at every round \(t\ge T(n,\delta )\).