Opinion forming in Erdős-Rényi random graph and expanders

DOI10.1016/J.DAM.2019.10.001MaRDI QIDQ2306607zbMATH OpenOpenAlexFDO

Authors Ahad N. Zehmakan

Publication date 23 March 2020

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

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

zbMATH Keywords

bootstrap percolationexpandersmajority modelrandom graphs

Mathematics Subject Classification ID

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

Abstract: Assume for a graph $G=(V,E)$ and an initial configuration, where each node is blue or red, in each discrete-time round all nodes simultaneously update their color to the most frequent color in their neighborhood and a node keeps its color in case of a tie. We study the behavior of this basic process, which is called majority model, on the binomial random graph $mathcal{G}_{n,p}$ and regular expanders. First we consider the behavior of the majority model in $mathcal{G}_{n,p}$ with an initial random configuration, where each node is blue independently with probability $p_b$ and red otherwise. It is shown that in this setting the process goes through a phase transition at the connectivity threshold, namely $fraclognn$. Furthermore, we discuss the majority model is a `good' and `fast' density classifier on regular expanders. More precisely, we prove if the second-largest absolute eigenvalue of the adjacency matrix of an $n$-node $Delta$-regular graph is sufficiently smaller than $Delta$ then the majority model by starting from $(frac12-delta)n$ blue nodes (for an arbitrarily small constant $delta>0$) results in fully red configuration in sub-logarithmically many rounds. As a by-product of our results, we show Ramanujan graphs are asymptotically optimally immune, that is for an $n$-node $Delta$-regular Ramanujan graph if the initial number of blue nodes is $$, the number of blue nodes in the next round is at most $fraccsDelta$ for some constants $$. This settles an open problem by Peleg.

Recommendations

• Opinion Forming in Erdös-Rényi Random Graph and Expanders
• Consensus Dynamics and Opinion Formation on Hypergraphs
• Perspectives on exponential random graphs
• Rumor spreading on random regular graphs and expanders
• Rumor spreading on random regular graphs and expanders
• scientific article; zbMATH DE number 1943957
• Expansion of random graphs: new proofs, new results
• A Density Description of a Bounded-Confidence Model of Opinion Dynamics on Hypergraphs
• Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion
• A bounded-confidence model of opinion dynamics on hypergraphs

Cites work

• A proof of alon's second eigenvalue conjecture
• Bootstrap percolation on the random regular graph
• Color War: Cellular Automata with Majority-Rule
• Comportement périodique des fonctions à seuil binaires et applications
• Consensus of interacting particle systems on Erdős-Rényi graphs
• Contagious sets in expanders
• Convergence in (social) influence networks
• Dynamic monopolies in tori.
• Dynamic monopolies in two-way bootstrap percolation
• Dynamic monopolies of constant size
• Eigenvalues and expanders
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Expander graphs and their applications
• scientific article; zbMATH DE number 3610746 (Why is no real title available?)
• scientific article; zbMATH DE number 1754618 (Why is no real title available?)
• scientific article; zbMATH DE number 6851888 (Why is no real title available?)
• scientific article; zbMATH DE number 3255204 (Why is no real title available?)
• Immunity against local influence
• Listen to Your Neighbors: How (Not) to Reach a Consensus
• Local majorities, coalitions and monopolies in graphs: A review
• Majority dynamics on trees and the dynamic cavity method
• Majority model on random regular graphs
• On pre-periods of discrete influence systems
• On the behavior of some cellular automata related to bootstrap percolation
• On time versus size for monotone dynamic monopolies in regular topologies
• Ramanujan graphs
• Random disease on the square grid
• Random majority percolation
• Rumour spreading and graph conductance
• Size bounds for dynamic monopolies
• Stretched exponential fixation in stochastic Ising models at zero temperature

Cited in

(16)

• 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
• Majority model on random regular graphs
• Central limit theorem for majority dynamics: bribing three voters suffices
• Opinion Forming in Erdös-Rényi Random Graph and Expanders
• Rumor spreading: A trigger for proliferation or fading away
• 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
• Asynchronous majority dynamics on binomial random graphs
• Phase transitions in biased opinion dynamics with 2-choices rule
• Opinion diffusion in graphs: an adversarial approach
• The ``power of few phenomenon: the sparse case

This page was built for publication: Opinion forming in Erdős-Rényi random graph and expanders

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