The edge-averaging process on graphs with random initial opinions

Abstract: 

In several settings (e.g., sensor networks and social networks), nodes of a graph are equipped with initial opinions, and the goal is to estimate the average of these opinions using local operations. A natural algorithm to achieve this is the edge-averaging process, where edges are repeatedly selected at random (according to independent Poisson clocks) and the opinions on the nodes of each selected edge are replaced by their average. The effectiveness of this algorithm is determined by its convergence rate. It is known that on a finite graph of n nodes, the opinions reach approximate consensus in polynomial time. We prove that the convergence is much faster when the initial opinions are disordered (independent identically distributed): the time to reach approximate consensus is O(log^2 n), and this bound is sharp. For infinite graphs, we show that for every p ≥ 1, if the initial opinions are in L^p, then the opinion at each vertex converges to the mean in L^p, and if p > 4, then almost sure convergence holds as well.