共查询到20条相似文献,搜索用时 15 毫秒
1.
In this note we analyse an anisotropic, two-dimensional bootstrap percolation model introduced by Gravner and Griffeath. We
present upper and lower bounds on the finite-size effects. We discuss the similarities with the semi-oriented model introduced
by Duarte. 相似文献
2.
3.
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\ge 2$ 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 $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 $\varepsilon > 0$ such that, with high probability, the final set of infected vertices has size at least $\varepsilon n$ . This behaviour is in sharp contrast with the case where the underlying graph is a $G(n, p)$ random graph with $p=d/n$ . It follows from an observation of Balogh and Bollobás 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 $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}$ . 相似文献
4.
Hamed Amini 《Journal of statistical physics》2010,141(3):459-475
Recent experimental studies of living neural networks reveal that their global activation induced by electrical stimulation
can be explained using the concept of bootstrap percolation on a directed random network. The experiment consists in activating
externally an initial random fraction of the neurons and observe the process of firing until its equilibrium. The final portion
of neurons that are active depends in a non linear way on the initial fraction. The main result of this paper is a theorem
which enables us to find the final proportion of the fired neurons, in the asymptotic case, in the case of random directed
graphs with given node degrees as the model for interacting network. This gives a rigorous mathematical proof of a phenomena
observed by physicists in neural networks. 相似文献
5.
Federico Camia 《Journal of statistical physics》2005,118(1-2):85-101
Consider a cellular automaton with state space {0,1} 2 where the initial configuration _0 is chosen according to a Bernoulli product measure, 1s are stable, and 0s become 1s if they are surrounded by at least three neighboring 1s. In this paper we show that the configuration _n at time n converges exponentially fast to a final configuration , and that the limiting measure corresponding to is in the universality class of Bernoulli (independent) percolation. More precisely, assuming the existence of the critical exponents , , and , and of the continuum scaling limit of crossing probabilities for independent site percolation on the close-packed version of 2 (i.e. for independent *-percolation on ), we prove that the bootstrapped percolation model has the same scaling limit and critical exponents.This type of bootstrap percolation can be seen as a paradigm for a class of cellular automata whose evolution is given, at each time step, by a monotonic and nonessential enhancement [Aizenman and Grimmett, J. Stat. Phys. 63: 817--835 (1991); Grimmett, Percolation, 2nd Ed.
(Springer, Berlin, 1999) 相似文献
6.
We consider an anisotropic independent bond percolation model on
, i.e. we suppose that the vertical edges of
are open with probability p and closed with probability 1–p, while the horizontal edges of
are open with probability p and closed with probability 1– p, with 0 < p, < 1. Let
, with x1 < x2, and
. It is natural to ask how the two point connectivity function Pp,({0 x}) behaves, and whether anisotropy in percolation probabilities implies the strict inequality Pp,({0 x})> Pp,({0 x}). In this note we give affirmative answer at least for some regions of the parameters involved.Mathematics Subject Classifications (2000). 82B20, 82B41, 82B43. 相似文献
7.
B. Ya. Balagurov 《Journal of Experimental and Theoretical Physics》2018,126(3):417-421
The metal–insulator and metal–superconductor phase transitions related to the percolation thresholds in two-component composites are considered. The behavior of effective conductivity σ e in the vicinity of both thresholds is described in terms of the similarity hypothesis. A one-to-one correspondence between the equations derived for σ e in both critical regions is found for randomly heterogeneous systems. 相似文献
8.
Bootstrap percolation is a type of cellular automaton on graphs, introduced as a simple model of the dynamics of ferromagnetism. Vertices in a graph can be in one of two states: ‘healthy’ or ‘infected’ and from an initial configuration of states, healthy vertices become infected by local rules. While the usual bootstrap processes are monotone in the sets of infected vertices, in this paper, a modification is examined in which infected vertices can return to a healthy state. Vertices are initially infected independently at random and the central question is whether all vertices eventually become infected. The model examined here is such a process on a square grid for which healthy vertices with at least two infected neighbours become infected and infected vertices with no infected neighbours become healthy. Sharp thresholds are given for the critical probability of initial infections for all vertices eventually to become infected. 相似文献
9.
An n×n×?×n hypercube is made from n d unit hypercubes. Two unit hypercubes are neighbours if they share a (d?1)-dimensional face. In each step of a dismantling process, we remove a unit hypercube that has precisely d neighbours. A move is balanced if the neighbours are in d orthogonal directions. In the extremal case, there are n d?1 independent unit hypercubes left at the end of the dismantling. We call this set of hypercubes a solution. If a solution is projected in d orthogonal directions and we get the entire [n] d?1 hypercube in each direction, then the solution is perfect. We show that it is possible to use a greedy algorithm to test whether a set of hypercubes forms a solution. Perfect solutions turn out to be precisely those which can be reached using only balanced moves. Every perfect solution corresponds naturally to a Latin hypercube. However, we show that almost all Latin hypercubes do not correspond to solutions. In three dimensions, we find at least n perfect solutions for every n, and we use our greedy algorithm to count the perfect solutions for n??6. We also construct an infinite family of imperfect solutions and show that the total size of its three orthogonal projections is asymptotic to the minimum possible value. Our results solve several conjectures posed in a proceedings paper by Barát, Korondi and Varga. If our dismantling process is reversed we get a build-up process very closely related to well-studied models of bootstrap percolation. We show that in an important special case our build-up reaches the same maximal position as bootstrap percolation. 相似文献
10.
Fran?ois Sausset Cristina Toninelli Giulio Biroli Gilles Tarjus 《Journal of statistical physics》2010,138(1-3):411-430
We study bootstrap percolation (BP) on hyperbolic lattices obtained by regular tilings of the hyperbolic plane. Our work is motivated by the connection between the BP transition and the dynamical transition of kinetically constrained models, which are in turn relevant for the study of glass and jamming transitions. We show that for generic tilings there exists a BP transition at a nontrivial critical density, 0<ρ c <1. Thus, despite the presence of loops on all length scales in hyperbolic lattices, the behavior is very different from that on Euclidean lattices where the critical density is either zero or one. Furthermore, we show that the transition has a mixed character since it is discontinuous but characterized by a diverging correlation length, similarly to what happens on Bethe lattices and random graphs of constant connectivity. 相似文献
11.
Achillefs Tzioufas 《Journal of statistical physics》2018,171(5):802-821
We consider the cardinality of supercritical oriented bond percolation in two dimensions. We show that, whenever the the origin is conditioned to percolate, the process appropriately normalized converges asymptotically in distribution to the standard normal law. This resolves a longstanding open problem pointed out to in several instances in the literature. The result applies also to the continuous-time analog of the process, viz. the basic one-dimensional contact process. We also derive general random-indices central limit theorems for associated random variables as byproducts of our proof. 相似文献
12.
13.
A lattice-based analysis of the percolation threshold for randomly distributed cylindrical particles is generalized to consider
arbitrary joint distributions over the radii and lengths of the rods. Effects due to the finite hard core diameter of the
particles are accounted for. An analogy to site percolation on a modified Bethe lattice is exploited to yield a result for
the percolation threshold that is equivalent to one that has been obtained from integral equation methods in the limit of
large aspect ratios for the rods. 相似文献
14.
Rodrigo G. Couto Bernardo N. B. de Lima Rémy Sanchis 《Journal of statistical physics》2013,153(5):739-750
We consider an anisotropic bond percolation model on $\mathbb{Z}^{2}$ , with p=(p h ,p v )∈[0,1]2, p v >p h , and declare each horizontal (respectively vertical) edge of $\mathbb{Z}^{2}$ to be open with probability p h (respectively p v ), and otherwise closed, independently of all other edges. Let $x=(x_{1},x_{2}) \in\mathbb{Z}^{2}$ with 0<x 1<x 2, and $x'=(x_{2},x_{1})\in\mathbb{Z}^{2}$ . It is natural to ask how the two point connectivity function $\mathbb{P}_{\mathbf{p}}(\{0\leftrightarrow x\})$ behaves, and whether anisotropy in percolation probabilities implies the strict inequality $\mathbb{P}_{\mathbf{p}}(\{0\leftrightarrow x\})>\mathbb{P}_{\mathbf {p}}(\{0\leftrightarrow x'\})$ . In this note we give an affirmative answer in the highly supercritical regime. 相似文献
15.
Neville Ball 《Journal of statistical physics》2014,156(3):574-585
We extend the method of Balister, Bollobás and Walters (Phys. Rev. E 76:011110, 2007) for determining rigorous confidence intervals for the critical threshold of two dimensional lattices to three (and higher) dimensional lattices. We describe a method for determining a full confidence interval and apply it to show that the critical threshold for bond percolation on the simple cubic lattice is between \(0.2485\) and \(0.2490\) with \(99.9999\,\%\) confidence, and the critical threshold for site percolation on the same lattice is between \(0.3110\) and \(0.3118\) with \(99.9999\,\%\) confidence. 相似文献
16.
Christian D. Lorenz Raechelle May Robert M. Ziff 《Journal of statistical physics》2000,98(3-4):961-970
Extensive Monte Carlo simulations were performed in order to determine the precise values of the critical thresholds for site (p
hcp
c, S
=0.199 255 5±0.000 001 0) and bond (p
hcp
c, B
=0.120 164 0±0.000 001 0) percolation on the hcp lattice to compare with previous precise measurements on the fcc lattice. Also, exact enumeration of the hcp and fcc lattices was performed and yielded generating functions and series for the zeroth, first, and second moments of both lattices. When these series and the values of p
c are compared to those for the fcc lattice, it is apparent that the site percolation thresholds are different; however, the bond percolation thresholds are equal within error bars, and the series only differ slightly in the higher order terms, suggesting the actual values are very close to each other, if not identical. 相似文献
17.
Following the methods proposed by Yonezawa, Sakamoto and Hori, we have calculated the percolation thresholds Pc, their error bars ΔPc, and the correlation length exponents v of a family of the Sierpinski carpets for the site percolation problems by making use of MonteCarlo simulations and finite size scaling. We have found the dependence of Pc and v on the fractal dimensionality Df and the lacunarity. We ascertain that the site percolation problems on a family of Sierpinski carpets with central cutouts and different D belong to different universal classes, and those on Sierpinski carpets with same Df but of different lacunarities belong to different universal classes. 相似文献
18.
Alain-Sol Sznitman 《Communications in Mathematical Physics》2003,240(1-2):123-148
We investigate in this work the asymptotic behavior of an anisotropic random walk on the supercritical cluster for bond percolation on d, d2. In particular we show that for small anisotropy the walk behaves in a ballistic fashion, whereas for strong anisotropy the walk is sub-diffusive. For arbitrary anisotropy, we also prove the directional transience of the walk and construct a renewal structure. 相似文献
19.
Martin T. Barlow Antal A. Járai Takashi Kumagai Gordon Slade 《Communications in Mathematical Physics》2008,278(2):385-431
We consider simple random walk on the incipient infinite cluster for the spread-out model of oriented percolation on . In dimensions d > 6, we obtain bounds on exit times, transition probabilities, and the range of the random walk, which establish that the
spectral dimension of the incipient infinite cluster is , and thereby prove a version of the Alexander–Orbach conjecture in this setting. The proof divides into two parts. One part
establishes general estimates for simple random walk on an arbitrary infinite random graph, given suitable bounds on volume
and effective resistance for the random graph. A second part then provides these bounds on volume and effective resistance
for the incipient infinite cluster in dimensions d > 6, by extending results about critical oriented percolation obtained previously via the lace expansion. 相似文献
20.
We present a coupled decreasing sequence of random walks on Z that dominate the edge process of oriented bond percolation in two dimensions. Using the concept of random walk in a strip, we describe an algorithm that generates an increasing sequence of lower bounds that converges to the critical probability
of oriented percolation pc. From the 7th term on, these lower bounds improve upon 0.6298, the best rigorous lower bound at present, establishing 0.63328
as a rigorous lower bound for pc. Finally, a Monte Carlo simulation technique is presented; the use thereof establishes 0.64450 as a non-rigorous five-digit-precision (lower) estimate
for pc.
Mathematics Subject Classification (1991): 60K35
Supported by CNPq (grant N.301637/91-1).
Supported by a grant from CNPq. 相似文献