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
Theorem 5.1 of Lovász, Random walks on graphs: a survey (1993), in the form of Theorem 33 of the survey of Becchetti, Clementi and Natale, Consensus dynamics: an overview (SIGACT News 2020). Two printed details need a minor correction: Lovász’s text defines \(\lambda \) as \(\min \{ |\lambda _2|,|\lambda _n|\} \), a slip for \(\max \) (with \(\min \) the bound would fail, e.g. on a connected bipartite graph), and Theorem 33 of the survey prints \(\sqrt{d(v)/d(v)}\) for \(\sqrt{d(v)/d(u)}\); the corrected form is formalized (details).
\(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
The random sequential (gossip) averaging of Boyd, Ghosh, Prabhakar and Shah, Randomized gossip algorithms (IEEE Trans. Inf. Theory 52, 2006), the source of equations (4) and (5) of the survey of Becchetti, Clementi and Natale.
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
Becchetti, Clementi, Natale, Pasquale and Trevisan, Find your place: simple distributed algorithms for community detection (SODA 2017; SIAM J. Comput. 2020), Theorem 3.2.
\(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 )\).
6 Averaging whenever you meet
Becchetti, Clementi, Manurangsi, Natale, Pasquale, Raghavendra, Trevisan, Average whenever you meet: opportunistic protocols for community detection (ESA 2018, arXiv:1703.05045). The proof of Theorem 4.1 needs a minor correction: its last step uses \(\mathbb E\| z^{(0)}\| ^2\le 1/n\), while for uniform signs \(\mathbb E\| z^{(0)}\| ^2=n-2\). The conclusion still holds, and the formal proof uses its own bookkeeping (details).
One uniformly random edge is activated per round; a node activated for the first time draws a uniform sign, and both endpoints take the average of their two values. The rounds are i.i.d. uniform darts of \(G\).
A uniform dart is a uniform edge; a node holds a value exactly when it has been activated, and the protocol’s values are those of the averaging process started from the coins \(\sigma \); the sum of the values is conserved.
Induction on the list of rounds; every edge carries two darts.
\(W_t\) is a symmetric projection, \(\mathbb E[W]=\bar W=I-L/2m\) is symmetric and doubly stochastic, \(\mathbb E[x^{(t)}]=\bar W^tx^{(0)}\) and \(\mathbb E\| Wx\| ^2=x^\top \bar Wx\).
\(G\) is \(d\)-regular with communities \(V_1\) and \(V_2=V_1^c\) of size \(n/2\), each node having \(b\) neighbours in the other community, \(0{\lt}b\), \(2b{\lt}d{\lt}n\). The state splits as \(x=x_\parallel +y+z\) along \(\mathbb 1\), \(\chi =\mathbb 1_{V_1}-\mathbb 1_{V_2}\) and their orthogonal complement; \(\lambda _2=2b/d\), and \(\lambda _3\) enters as a lower bound on the Rayleigh quotient of \(L/d\) on the complement.
\(\bar W\chi =(1-\lambda _2/n)\chi \), the expected state decomposes exactly as in Lemma B.1, and the monotonicity and sign criteria of Lemmas B.3 and B.4 hold at every node.
\(\bar W\) contracts the complement of \(\operatorname {span}\{ \mathbb 1,\chi \} \) by \(1-\lambda _3/n\).
With \(\beta =\langle x,\chi \rangle /n\): \(\mathbb E\| z'\| ^2\le (1-\lambda _3/n)\| z\| ^2+\lambda _2\beta ^2\) and, for every \(\gamma \), \(\mathbb E\, n(\beta '-\gamma )^2\le (1-\lambda _2/n)\, n(\beta -\gamma )^2+\lambda _2\gamma ^2 +(4\lambda _2/n^2)(n\beta ^2+\| z\| ^2)\).
\(\mathbb E\| Wx\| ^2=x^\top \bar Wx\) and Jensen for \(\beta '\); the variance of \(\beta '\) comes from the \(nb\) darts across the cut.
If \(100\lambda _2\log n\le \lambda _3\) and \(3(n/\lambda _3)\log n\le t\le n/(4\lambda _2)\), then \(\mathbb E\| y^{(t)}+z^{(t)}-y^{(0)}\| ^2\le 3\lambda _2t/n\).
Unroll the two recursions from any state; average over the signs (\(\mathbb E\| y^{(0)}\| ^2=1\), \(\| z^{(0)}\| ^2\le n\)).
If \(\lambda _2/\lambda _3\le \lambda _3\varepsilon ^4/(c\log ^2n)\), then with probability at least \(1-\varepsilon \) at least \((1-3\varepsilon )n\) nodes are \(\varepsilon \)-good at every round of the phase \(6(n/\lambda _3)\log n\le t\le 12(n/\lambda _3)\log n\).
Good nodes averaged only with good nodes of their community stay good; the bad rounds of the phase are counted in expectation from the second-moment bounds restarted at the start of the phase, and small initial cut components are handled by anti-concentration of \(\langle \sigma ,\chi \rangle \).
Under the hypothesis of Lemma 4.2, with probability at least \(1-4\varepsilon \) at least \((1-4\varepsilon )n\) nodes have the sign of their community’s initial average throughout the phase, and with probability at least \(1/2-6\varepsilon \) the signs of the values are a \(6\varepsilon \)-weak reconstruction at every round of the phase.
A good node has the sign of \(2S_h/n\) unless \(|S_1|\le \varepsilon |S_2|\) or \(|S_2|\le \varepsilon |S_1|\) (each of probability at most \(\varepsilon +1/\sqrt{n/2+1}\)); \(S_1S_2{\lt}0\) with probability at least \(1/2-1/\sqrt{n/2+1}\).