Distributed Averaging in Opinion Dynamics

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

62 Downloads (Pure)

Abstract

We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node u of the graph has an initial value ζu(0). In the first process, which we call the NodeModel, at each time step t ≥ 0, a random node u and a random sample of k of its neighbours v1, v2, ⋯ , vk are selected. Then, u updates its current value ζu(t) to [EQUATION], where α ĝ (0, 1) and k ≥ 1 are parameters of the process. In the second process, called the EdgeModel, at each step a random pair of adjacent nodes (u, v) is selected, and then node u updates its value equivalently to the NodeModel with k = 1 and v as the selected neighbour.For both processes, the values of all nodes converge to the same value F, which is a random variable depending on the random choices made in each step. For the NodeModel and regular graphs, and for the EdgeModel and arbitrary graphs, the expectation of F is the average of the initial values [EQUATION]. For the NodeModel and non-regular graphs, the expectation of F is the degree-weighted average of the initial values.Our results are two-fold. We consider the concentration of F and show tight bounds on the variance of F for regular graphs. We show that when the initial values do not depend on the number of nodes, then the variance is negligible, and hence the nodes are able to estimate the initial average of the node values. Interestingly, this variance does not depend on the graph structure. For the proof we introduce a duality between our processes and a process of two correlated random walks. We also analyse the convergence time for both models and for arbitrary graphs, showing bounds on the time Tϵ required to make all node values 'ϵ-close' to each other. Our bounds are asymptotically tight under some assumptions on the distribution of the initial values.

Original languageEnglish
Title of host publicationProceedings of the 2023 ACM Symposium on Principles of Distributed Computing
PublisherACM
Pages211-221
Number of pages11
ISBN (Electronic)9798400701214
DOIs
Publication statusPublished - 16 Jun 2023

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Fingerprint

Dive into the research topics of 'Distributed Averaging in Opinion Dynamics'. Together they form a unique fingerprint.

Cite this