Opinion forming in Erdős–Rényi random graph and expanders
METADATA ONLY
Loading...
Author / Producer
Date
2020-04-30
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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 the majority model, on the Erdős–Rényi random graph Gn,p and regular expanders. First we consider the behavior of the majority model on Gn,p with an initial random configuration, where each node is blue independently with probability pb and red otherwise. It is shown that in this setting the process goes through a phase transition at the connectivity threshold, namely logn∕n. Furthermore, we say a graph G is λ-expander if the second-largest absolute eigenvalue of its adjacency matrix is λ. We prove that for a Δ-regular λ-expander graph if λ∕Δ is sufficiently small, then the majority model by starting from 1∕2−δn blue nodes (for an arbitrarily small constant δ>0) results in fully red configuration in sub-logarithmically many rounds. Roughly speaking, this means the majority model is an “efficient” and “fast” density classifier on regular expanders. As a by-product of our results, we show that regular Ramanujan graphs are asymptotically optimally immune, that is for an n-node Δ-regular Ramanujan graph if the initial number of blue nodes is s≤βn, the number of blue nodes in the next round is at most cs∕Δ for some constants c,β>0. © 2019 Elsevier B.V.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
277
Pages / Article No.
280 - 290
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Expanders; Random graphs; Majority model; Bootstrap percolation
Organisational unit
09687 - Kyng, Rasmus / Kyng, Rasmus
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)