The edge-averaging process on graphs with random initial opinions

Dor Elboim, Yuval Peres () and Ron Peretz ()
Additional contact information
Dor Elboim: a Department of mathematics , Stanford University , Stanford , CA 94305
Yuval Peres: b Beijing Institute of Mathematical Sciences and Applications , Beijing 101408 , China
Ron Peretz: c Department of Economics , Bar Ilan University , Ramat Gan 5290002 , Israel

Proceedings of the National Academy of Sciences, 2025, vol. 122, issue 33, e2423947122

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.

Keywords: averaging process; opinion dynamics; consensus (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1073/pnas.2423947122 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nas:journl:v:122:y:2025:p:e2423947122

Access Statistics for this article

More articles in Proceedings of the National Academy of Sciences from Proceedings of the National Academy of Sciences
Bibliographic data for series maintained by PNAS Product Team ().