CaltechAUTHORS
  A Caltech Library Service

Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs

Benjamini, Itai and Chan, Siu-On and O'Donnell, Ryan and Tamuz, Omer and Tan, Li-Yang (2014) Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs. . (Submitted) https://resolver.caltech.edu/CaltechAUTHORS:20161111-145123837

[img] PDF - Submitted Version
See Usage Policy.

220Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161111-145123837

Abstract

In majority dynamics, agents located at the vertices of an undirected simple graph update their binary opinions synchronously by adopting those of the majority of their neighbors. On infinite unimodular transitive graphs (e.g., Cayley graphs), when initial opinions are chosen from a distribution that is invariant with respect to the graph automorphism group, we show that the opinion of each agent almost surely either converges, or else eventually oscillates with period two; this is known to hold for finite graphs, but not for all infinite graphs. On Erdős-Rényi random graphs with degrees Ω(n√), we show that when initial opinions are chosen i.i.d. then agents all converge to the initial majority opinion, with constant probability. Conversely, on random 4-regular finite graphs, we show that with high probability different agents converge to different opinions.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
https://arxiv.org/abs/1405.2486arXivDiscussion Paper
ORCID:
AuthorORCID
Tamuz, Omer0000-0002-0111-0418
Additional Information:R. O’Donnell is supported by NSF grants CCF-1319743 and CCF-1116594.
Funders:
Funding AgencyGrant Number
NSFCCF-1319743
NSFCCF-1116594
Record Number:CaltechAUTHORS:20161111-145123837
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20161111-145123837
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71961
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:16 Nov 2016 00:23
Last Modified:03 Oct 2019 16:13

Repository Staff Only: item control page