Opinion Forming in Erdös-Rényi Random Graph and Expanders
Opinion Forming in Erdös-Rényi Random Graph and Expanders
复制标题
Erdös-Rényi 随机图和扩展器中的意见形成
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Ahad N. Zehmakan
中科院分区：
文献类型：
--
作者：
Ahad N. Zehmakan
假设图G =（V，E）和初始配置，其中每个节点是蓝色或红色，在每个离散时间轮中，所有节点同时将其颜色更新为其邻域中最常见的颜色，并且节点在平局的情况下保持其颜色。本文研究了这一基本过程在Erdos-Renyi随机图G_{n，p}和正则扩张子上的行为。首先考虑G_{n，p}上的多数模型的行为，其中每个节点以概率p_B独立地为蓝色，否则为红色。结果表明，在这种设置的过程中，通过一个相变的连通性阈值，即（log n）/n。此外，如果图G的邻接矩阵的第二大绝对特征值是λ，则称图G是λ-扩张图。证明了对于Delta-正则图，如果lambda/Delta足够小，则从（1/2-delta）n个蓝色节点（对于任意小的常数delta> 0）开始的多数模型在次代数上的许多轮中都能得到完全红色的配置.粗略地说，这意味着多数模型是一个“高效”和“快速”的密度分类器。作为我们的结果的一个副产品，我们证明了正则Ramanujan图是渐近最优免疫的，也就是说，对于一个n-节点Delta-正则Ramanujan图，如果蓝色节点的初始数量是s 0。这解决了Peleg的一个开放问题[Peleg，2014]。
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 Erdos-Renyi 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 0. This settles an open problem by Peleg [Peleg, 2014].