The edge-averaging process on graphs with random initial opinions.

Authors

Dor Elboim, Yuval Peres, Ron Peretz

Published in

Proceedings of the National Academy of Sciences of the United States of America. Volume 122. Issue 33. Pages e2423947122. Aug 19, 2025. Epub Aug 15, 2025.

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.

PMID:
40815627
Bibliographic data and abstract were imported from PubMed on 16 Aug 2025.

Read full publication at:
Please sign in to see all details.

Stats

1-terrible, 9-excellent. How would you rate this publication? Sign in in to submit your rating.

Post a comment

You need to be signed in to post comments. You can sign in here.

Comments

There are no comments yet.