Bootstrap Percolation in Power-Law Random Graphs
Bootstrap Percolation in Power-Law Random Graphs
复制标题
DOI：
10.1007/s10955-014-0946-6
复制
发表时间：
2014-04-01
影响因子：
1.6
通讯作者：
Fountoulakis, Nikolaos
中科院分区：
文献类型：
--
作者：
Amini, Hamed;Fountoulakis, Nikolaos
图上的自举逾渗过程是一个逐轮演化的“感染”过程。最初，有一个受感染节点的子集，在随后的每一轮中，至少有受感染邻居的每个未受感染节点都被感染，并永远保持感染状态。参数是固定的。此类过程已被用作个人网络内思想或趋势传播的模型。我们分析这个过程中的情况下，底层图是一个非均匀的随机图，表现出幂律度分布，最初有随机感染的节点。本文的主要焦点是在过程结束时将被感染的顶点的数量。本文的主要结果是，如果随机图的度序列服从指数幂律，其中，则初始感染顶点的次线性数量足以以高概率将感染传播到随机图的线性分数节点上。更具体地说，我们明确地确定一个临界函数，使得具有以下性质。假设这是底层随机图的顶点数，如果，则该过程根本不进化，并且随着增长而具有高概率，而如果，则存在一个常数，使得最终的感染顶点集具有高概率，至少具有大小。这种行为与底层图是随机图的情况形成鲜明对比。从Balogh和Bollobas的观察可以看出，在这种情况下，如果最初感染的顶点数是次线性的，那么这个过程就没有进化。当最大度为时，则还取决于。但当最大度数为时，则。
A bootstrap percolation process on a graph 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 infected neighbours becomes infected and remains so forever. The parameter is fixed. Such processes have been used as models for the spread of ideas or trends within a network of individuals. 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 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 , 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 such that with the following property. Assuming that is the number of vertices of the underlying random graph, if , then the process does not evolve at all, with high probability as grows, whereas if , then there is a constant such that, with high probability, the final set of infected vertices has size at least . This behaviour is in sharp contrast with the case where the underlying graph is a random graph with . It follows from an observation of Balogh and Bollobas that in this case if the number of initially infected vertices is sublinear, then there is lack of evolution of the process. It turns out that when the maximum degree is , then depends also on . But when the maximum degree is , then .