Majority model on random regular graphs

DOI10.1007/978-3-319-77404-6_42MaRDI QIDQ2294715zbMATH OpenOpenAlexFDO

Authors B. Gärtner, Ahad N. Zehmakan

Publication date 12 February 2020

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

zbMATH Keywords

bootstrap percolationdensity classificationdynamic monopolymajority modelrandom regular graphthreshold behavior

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: Consider a graph $G=(V,E)$ and an initial random coloring where each vertex $vinV$ is blue with probability $P_b$ and red otherwise, independently from all other vertices. In each round, all vertices simultaneously switch their color to the most frequent color in their neighborhood and in case of a tie, a vertex keeps its current color. The main goal of the present paper is to analyze the behavior of this basic and natural process on the random $d$-regular graph $mathbb{G}_{n,d}$. It is shown that for all $epsilon>0$, $P_{b}le1/2-epsilon$ results in final complete occupancy by red in $mathcalO(lo{g}_{d}logn)$ rounds with high probability, provided that $dgeqc/epsilo{n}^2$ for a suitable constant $c$. Furthermore, we show that with high probability, $mathbb{G}_{n,d}$ is immune; i.e., the smallest dynamic monopoly is of linear size. A dynamic monopoly is a subset of vertices that can take over in the sense that a commonly chosen initial color eventually spreads throughout the whole graph, irrespective of the colors of other vertices. This answers an open question of Peleg.

Recommendations

• Resolution of a conjecture on majority dynamics: rapid stabilization in dense random graphs
• Opinion forming in Erdős-Rényi random graph and expanders
• Majority dynamics on sparse random graphs
• Dynamic monopolies in tori.
• Central limit theorem for majority dynamics: bribing three voters suffices

Cited in

(30)

• The majority action on infinite graphs: Strings and puppets
• Threshold behavior of democratic opinion dynamics
• A note on the majority dynamics in inhomogeneous random graphs
• On the spread of influence in graphs
• Majority dynamics and the median process: connections, convergence and some new conjectures
• Threshold behavior of bootstrap percolation
• Majority rule cellular automata
• Opinion forming in Erdős-Rényi random graph and expanders
• Dynamic monopolies in two-way bootstrap percolation
• Central limit theorem for majority dynamics: bribing three voters suffices
• Resolution of a conjecture on majority dynamics: rapid stabilization in dense random graphs
• Local majority dynamics on preferential attachment graphs
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• Global majority consensus by local majority polling on graphs of a given degree sequence
• Opinion Forming in Erdös-Rényi Random Graph and Expanders
• The power of small coalitions under two-tier majority on regular graphs
• Majority dynamics on sparse random graphs
• Phase transition of the k-majority dynamics in biased communication models
• Majority vote in social networks
• The Structure of Configurations in One-Dimensional Majority Cellular Automata: From Cell Stability to Configuration Periodicity
• Dynamic monopolies with randomized starting configuration
• Target set in threshold models
• Quasi-majority functional voting on expander graphs
• Quasi-majority functional voting on expander graphs
• A general stabilization bound for influence propagation in graphs
• Testing spreading behavior in networks with arbitrary topologies
• Asynchronous majority dynamics on binomial random graphs
• Majority dynamics on random graphs: the multiple states case
• Phase transitions in biased opinion dynamics with 2-choices rule
• Opinion diffusion in graphs: an adversarial approach

This page was built for publication: Majority model on random regular graphs

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