اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدBootstrap percolation in inhomogeneous random graphs
187
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 every uninfected node which has at least r infected neighbours becomes infected and remains so forever. The parameter r > 1 is fixed. We consider this process in the case where the underlying graph is an inhomogeneous random graph whose kernel is of rank 1. Assuming that initially every vertex is infected independently with probability p > 0, we provide a law of large numbers for the number of vertices that will have been infected by the end of the process. We also focus on a special case of such random graphs which exhibit a power-law degree distribution with exponent in (2,3). The first two authors have shown the existence of a critical function a_c(n) such that a_c(n)=o(n) with the following property. Let n be the number of vertices of the underlying random graph and let a(n) be the number of the vertices that are initially infected. Assume that a set of a(n) vertices is chosen randomly and becomes externally infected. If a(n) << a_c(n), then the process does not evolve at all, with high probability as n grows, whereas if a(n)>> a_c(n), then with high probability the final set of infected vertices is linear. Using the techniques of the previous theorem, we give the precise asymptotic fraction of vertices which will be eventually infected when a(n) >> a_c (n) but a(n) = o(n). Note that this corresponds to the case where p approaches 0.
قيم البحث
اقرأ أيضاً
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 infect
ed and remains so forever. The parameter $rgeq 2$ is fixed. Such processes have been used as models for the spread of ideas or trends within a network of individuals. We analyse bootstrap percolation 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 $beta$, where $2 < beta < 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 $a_c(n)$ such that $a_c(n)=o(n)$ with the following property. Assuming that $n$ is the number of vertices of the underlying random graph, if $a(n) ll a_c(n)$, then the process does not evolve at all, with high probability as $n$ grows, whereas if $a(n)gg a_c(n)$, then there is a constant $eps>0$ such that, with high probability, the final set of infected vertices has size at least $eps n$. It turns out that when the maximum degree is $o(n^{1/(beta -1)})$, then $a_c(n)$ depends also on $r$. But when the maximum degree is $Theta (n^{1/(beta -1)})$, then $a_c (n)=n^{beta -2 over beta -1}$.
We study the critical probability for the metastable phase transition of the two-dimensional anisotropic bootstrap percolation model with $(1,2)$-neighbourhood and threshold $r = 3$. The first order asymptotics for the critical probability were recen
tly determined by the first and second authors. Here we determine the following sharp second and third order asymptotics: [ p_cbig( [L]^2,mathcal{N}_{(1,2)},3 big) ; = ; frac{(log log L)^2}{12log L} , - , frac{log log L , log log log L}{ 3log L} + frac{left(log frac{9}{2} + 1 pm o(1) right)log log L}{6log L}. ] We note that the second and third order terms are so large that the first order asymptotics fail to approximate $p_c$ even for lattices of size well beyond $10^{10^{1000}}$.
We show that the contact process on the rank-one inhomogeneous random graphs and Erdos-R{e}nyi graphs with mean degree large enough survives a time exponential in the size of these graphs for any positive infection rate. In addition, a metastable result for the extinction time is also proved.
Bootstrap percolation on a graph iteratively enlarges a set of occupied sites by adjoining points with at least $theta$ occupied neighbors. The initially occupied set is random, given by a uniform product measure, and we say that spanning occurs if e
very point eventually becomes occupied. The main question concerns the critical probability, that is, the minimal initial density that makes spanning likely. The graphs we consider are products of cycles of $m$ points and complete graphs of $n$ points. The major part of the paper focuses on the case when two factors are complete graphs and one factor is a cycle. We identify the asymptotic behavior of the critical probability and show that, when $theta$ is odd, there are two qualitatively distinct phases: the transition from low to high probability of spanning as the initial density increases is sharp or gradual, depending on the size of $m$.
Let $mathbb{G}=left(mathbb{V},mathbb{E}right)$ be the graph obtained by taking the cartesian product of an infinite and connected graph $G=(V,E)$ and the set of integers $mathbb{Z}$. We choose a collection $mathcal{C}$ of finite connected subgraphs o
f $G$ and consider a model of Bernoulli bond percolation on $mathbb{G}$ which assigns probability $q$ of being open to each edge whose projection onto $G$ lies in some subgraph of $mathcal{C}$ and probability $p$ to every other edge. We show that the critical percolation threshold $p_{c}left(qright)$ is a continuous function in $left(0,1right)$, provided that the graphs in $mathcal{C}$ are well-spaced in $G$ and their vertex sets have uniformly bounded cardinality. This generalizes a recent result due to Szabo and Valesin.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
