Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 16, 2016 | Submitted
Report Open

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


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.

Additional Information

R. O'Donnell is supported by NSF grants CCF-1319743 and CCF-1116594.

Attached Files

Submitted - 1405.2486.pdf


Files (226.1 kB)
Name Size Download all
226.1 kB Preview Download

Additional details

August 20, 2023
October 23, 2023