What I Tell You Three Times Is True: Bootstrap Percolation in Small Worlds
What I Tell You Three Times Is True: Bootstrap Percolation in Small Worlds
复制标题
我告诉你三遍的是真的：小世界中的引导渗透
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
N. Fountoulakis
中科院分区：
文献类型：
--
作者：
H. Amini;N. Fountoulakis
图G上的自举渗流过程是一个按轮演化的“感染”过程。最初，有一个受感染节点的子集，在随后的每一轮中，至少有r个受感染邻居的每个未受感染节点都被感染，并永远保持感染状态。参数r ≥ 2是固定的。
我们分析这个过程的情况下，底层图是一个非均匀的随机图，它表现出幂律度分布，最初有一个（n）随机感染节点。本文的主要焦点是在过程结束时将被感染的顶点的数量。这项工作的主要结果是，如果随机图的度序列遵循指数为β的幂律，其中2<β<3，则初始感染顶点的次线性数量足以以高概率将感染传播到随机图的线性部分节点上。
更具体地说，我们明确地确定了一个临界函数ac（n），使得ac（n）=o（n）具有以下性质。假设n是底层随机图的顶点数，如果a（n）≥ ac（n），则过程根本不演化，并且随着n的增长具有很高的概率，而如果a（n）≥ ac（n），则存在常数e>0，使得最终的感染顶点集具有很高的概率具有至少en的大小。这种行为与底层图是G（n，p）随机图且p=d/n的情况形成鲜明对比。Janson，J.D.，Turova和Vallier最近的结果表明，如果初始感染顶点的数量是次线性的，那么最终感染顶点集的大小很有可能近似等于a（n）。也就是说，基本上缺乏过程的演变。
当最大次数为o（n1/（β−1））时，ac（n）也依赖于r。但当最大度为Θ（n1/（β−1））时，则$a_c（n）=n^{eta -2完毕 eta -1}$。
A bootstrap percolation process on a graph G is an "infection" process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round each uninfected node which has at least r infected neighbours becomes infected and remains so forever. The parameter r ≥ 2 is fixed.
We analyse this process in the case where the underlying graph is an inhomogeneous random graph, which exhibits a power-law degree distribution, and initially there are a(n) randomly infected nodes. The main focus of this paper is the number of vertices that will have been infected by the end of the process. The main result of this work is that if the degree sequence of the random graph follows a power law with exponent β, where 2<β<3, then a sublinear number of initially infected vertices is enough to spread the infection over a linear fraction of the nodes of the random graph, with high probability.
More specifically, we determine explicitly a critical function ac(n) such that ac(n)=o(n) with the following property. Assuming that n is the number of vertices of the underlying random graph, if a(n)≪ac(n), then the process does not evolve at all, with high probability as n grows, whereas if a(n)≫ac(n), then there is a constant e>0 such that, with high probability, the final set of infected vertices has size at least en. This behaviour is in sharp contrast with the case where the underlying graph is a G(n,p) random graph with p=d/n. Recent results of Janson, Łuczak, Turova and Vallier have shown that if the number of initially infected vertices is sublinear, then with high probability the size of the final set of infected vertices is approximately equal to a(n). That is, essentially there is lack of evolution of the process.
It turns out that when the maximum degree is o(n1/(β−1)), then ac(n) depends also on r. But when the maximum degree is Θ(n1/(β−1)), then $a_c (n)=n^{eta -2 over eta -1}$.