2026-07-20T11:16:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9952 2024-03-06T10:45:11Z ddc:004 open_access

Opinion Forming in Erdös-Rényi Random Graph and Expanders N. Zehmakan, Ahad majority model random graph expander graphs dynamic monopoly bootstrap percolation 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 Erdös-Rényi random graph G_{n,p} and regular expanders. First we consider the behavior of the majority model on 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 (log n)/n. Furthermore, we say a graph G is lambda-expander if the second-largest absolute eigenvalue of its adjacency matrix is lambda. We prove that for a Delta-regular lambda-expander graph if lambda/Delta is sufficiently small, then the majority model by starting from (1/2-delta)n blue nodes (for an arbitrarily small constant delta>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 regular Ramanujan graphs are asymptotically optimally immune, that is for an n-node Delta-regular Ramanujan graph if the initial number of blue nodes is s <= beta n, the number of blue nodes in the next round is at most cs/Delta for some constants c,beta>0. This settles an open problem by Peleg [Peleg, 2014]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ahad N. Zehmakan 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.4 urn:nbn:de:0030-drops-99529 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.4 eng https://creativecommons.org/licenses/by/3.0/legalcode