Distributed Averaging in Opinion Dynamics

DOI10.1145/3583668.3594593MaRDI QIDQ6202249zbMATH OpenOpenAlexWikidataFDO

Authors Petra Berenbrink, Colin Cooper, David Kohan Marzagão, Frederik Mallmann-Trenn, Tomasz Radzik, Nicolás Rivera

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.17125

zbMATH Keywords

distributed averagingdual processesrandom walksstochastic processes

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node $u$ has an initial value $x{i}_u(0)$. In the first process, the NodeModel, at each time step $tge0$, a random node $u$ and a random sample of $k$ of its neighbours $v_1,v_2,cdots,v_k$ are selected. Then, $u$ updates its current value $x{i}_u(t)$ to $x{i}_u(t+1)=alphax{i}_u(t)+frac(1-alpha)ksu{m}_{i=1}^{k}x{i}_{v_i}(t)$, where $alphain(0,1)$ and $kge1$ are parameters of the process. In the second process, 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 $F$, 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 $frac1nsu{m}_{uinV}x{i}_u(0)$. 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, 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_{v}arepsilon$ required to make all node values `$varepsilon$-close' to each other. Our bounds are asymptotically tight under assumptions on the distribution of the initial values.

Cites work

• A lecture on the averaging process
• A polylogarithmic gossip algorithm for plurality consensus
• A simple population protocol for fast robust approximate majority
• Bounds on the Voter Model in Dynamic Networks
• Broadcast and Gossip Stochastic Average Consensus Algorithms in Directed Topologies
• Coalescing random walks and voting on graphs
• Computing separable functions via gossip
• Convergence to equilibrium in local interaction games
• Diffusive influence systems
• Distributed probabilistic polling and applications to proportionate agreement
• Efficient plurality consensus, or: the benefits of cleaning up from time to time
• Fast plurality consensus in regular expanders
• First- and second-order diffusive methods for rapid, coarse, distributed load balancing
• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• Ignore or comply? On breaking symmetry in consensus
• Interacting particle systems as stochastic social dynamics
• Near-perfect load balancing by randomized rounding
• On the convergence of the Hegselmann-Krause system
• Opinion dynamics in social networks with stubborn agents: equilibrium and convergence rate
• Opinion dynamics with limited information
• Polynomial anonymous dynamic distributed computing without a unique leader
• Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations
• Randomized load balancing on networks with stochastic inputs
• Reaching a Consensus
• Social influence and opinions
• The Power of Two Choices in Distributed Voting
• Threshold behaviour of discordant voting on the complete graph

This page was built for publication: Distributed Averaging in Opinion Dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202249)