N. Zehmakan, Ahad
Opinion Forming in ErdösRényi Random Graph and Expanders
Abstract
Assume for a graph G=(V,E) and an initial configuration, where each node is blue or red, in each discretetime 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ösRé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 lambdaexpander if the secondlargest absolute eigenvalue of its adjacency matrix is lambda. We prove that for a Deltaregular lambdaexpander graph if lambda/Delta is sufficiently small, then the majority model by starting from (1/2delta)n blue nodes (for an arbitrarily small constant delta>0) results in fully red configuration in sublogarithmically many rounds. Roughly speaking, this means the majority model is an "efficient" and "fast" density classifier on regular expanders. As a byproduct of our results, we show regular Ramanujan graphs are asymptotically optimally immune, that is for an nnode Deltaregular 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].
BibTeX  Entry
@InProceedings{nzehmakan:LIPIcs:2018:9952,
author = {Ahad N. Zehmakan},
title = {{Opinion Forming in Erd{\"o}sR{\'e}nyi Random Graph and Expanders}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {4:14:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9952},
URN = {urn:nbn:de:0030drops99529},
doi = {10.4230/LIPIcs.ISAAC.2018.4},
annote = {Keywords: majority model, random graph, expander graphs, dynamic monopoly, bootstrap percolation}
}
06.12.2018
Keywords: 

majority model, random graph, expander graphs, dynamic monopoly, bootstrap percolation 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

06.12.2018 