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

DOI10.1016/j.dam.2014.07.026zbMath1303.05031arXiv1209.5025OpenAlexW2121696574MaRDI QIDQ476295

Moez Draief, Mohammed Amin Abdullah

Publication date: 28 November 2014

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

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

zbMATH Keywords

social networksdistributed computingconsensuslocal majority

Mathematics Subject Classification ID

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

Related Items (13)

On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols ⋮ On convergence and threshold properties of discrete Lotka-Volterra population protocols ⋮ Simple dynamics for plurality consensus ⋮ Central limit theorem for majority dynamics: bribing three voters suffices ⋮ Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models ⋮ Phase transition of the \(k\)-majority dynamics in biased communication models ⋮ Unnamed Item ⋮ Brief Announcement: Discrete Incremental Voting ⋮ Probabilistic consensus via polling and majority rules ⋮ Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs ⋮ Noisy rumor spreading and plurality consensus ⋮ Phase transition of the 3-majority dynamics with uniform communication noise ⋮ Majority dynamics and the median process: connections, convergence and some new conjectures

Cites Work

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

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