Phase Transitions of the k-Majority Dynamics in a Biased Communication Model
Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, Sara Rizzo
Abstract
Consider a graph where each of the n nodes is in one of two possible states, say or . Herein, we analyze the synchronous k-majoritydynamics, where nodes sample k neighbors uniformly at random with replacement and adopt the majority binary state among the nodes in the sample (potential ties are broken uniformly at random). This class of dynamics generalizes other well-known dynamics, e.g., voter and 3-majority, which have been studied in the literature as distributed algorithms for consensus.
Topics & Concepts
Voter modelDynamics (music)Binary numberComputer scienceSample (material)Random graphGraphDiscrete mathematicsClass (philosophy)Statistical physicsTheoretical computer scienceMathematicsCombinatoricsPhysicsArtificial intelligenceThermodynamicsArithmeticAcousticsOpinion Dynamics and Social InfluenceComplex Network Analysis TechniquesGame Theory and Applications