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 [Formula: see text] 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 [Formula: see text], and this bound is sharp. For infinite graphs, we show that for every [Formula: see text], if the initial opinions are in [Formula: see text], then the opinion at each vertex converges to the mean in [Formula: see text], and if [Formula: see text], then almost sure convergence holds as well.