Global majority consensus by local majority polling on graphs of a given degree sequence

DOI10.1016/J.DAM.2014.07.026zbMATH Open1303.05031arXiv1209.5025OpenAlexW2121696574MaRDI QIDQ476295FDOQ476295

Authors: Moez Draief, Mohammed Abdullah 

Publication date: 28 November 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Suppose in a graph $G$ vertices can be either red or blue. Let $k$ be odd. At each time step, each vertex $v$ in $G$ polls $k$ random neighbours and takes the majority colour. If it doesn't have $k$ neighbours, it simply polls all of them, or all less one if the degree of $v$ is even. We study this protocol on graphs of a given degree sequence, in the following setting: initially each vertex of $G$ is red independently with probability $alpha<frac12$, and is otherwise blue. We show that if $alpha$ is sufficiently biased, then with high probability consensus is reached on the initial global majority within $O(lo{g}_{k}lo{g}_{k}n)$ steps if $5leqkleqd$, and $O(lo{g}_{d}lo{g}_{d}n)$ steps if $k>d$. Here, $dgeq5$ is the effective minimum degree, the smallest integer which occurs $Theta(n)$ times in the degree sequence. We further show that on such graphs, any local protocol in which a vertex does not change colour if all its neighbours have that same colour, takes time at least $Omega(lo{g}_{d}lo{g}_{d}n)$, with high probability. Additionally, we demonstrate how the technique for the above sparse graphs can be applied in a straightforward manner to get bounds for the ErdH{o}s-R'enyi random graphs in the connected regime.

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

Recommendations

• Local majority dynamics on preferential attachment graphs
• Majority dynamics on sparse random graphs
• Simple dynamics for plurality consensus
• Majority model on random regular graphs
• The Match-Maker: Constant-Space Distributed Majority via Random Walks

zbMATH Keywords

social networksdistributed computingconsensuslocal majority

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Distributed systems (68M14)

Cites Work

• Concentration of Measure for the Analysis of Randomized Algorithms
• Multiple random walks in random regular graphs
• Cover time of a random graph with given degree sequence
• Distributed probabilistic polling and applications to proportionate agreement
• An Upper Bound on the Convergence Time for Quantized Consensus of Arbitrary Static Graphs
• Probabilistic consensus via polling and majority rules

Cited In (19)

• Noisy rumor spreading and plurality consensus
• Majority dynamics and the median process: connections, convergence and some new conjectures
• Title not available (Why is that?)
• Local majority dynamics on preferential attachment graphs
• Resolution of a conjecture on majority dynamics: rapid stabilization in dense random graphs
• Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
• Flip colouring of graphs
• Simple dynamics for plurality consensus
• Probabilistic consensus via polling and majority rules
• Central limit theorem for majority dynamics: bribing three voters suffices
• Brief Announcement: Discrete Incremental Voting
• Quasi-majority functional voting on expander graphs
• Title not available (Why is that?)
• Phase transition of the 3-majority opinion dynamics with noisy interactions
• Phase transition of the \(k\)-majority dynamics in biased communication models
• On convergence and threshold properties of discrete Lotka-Volterra population protocols
• On convergence and threshold properties of discrete Lotka-Volterra population protocols
• A tight analysis of the parallel undecided-state dynamics with two colors
• Phase transition of the 3-majority dynamics with uniform communication noise

This page was built for publication: Global majority consensus by local majority polling on graphs of a given degree sequence

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