Scale-free percolation

Maria Deijfen; Remco van der Hofstad; Gerard Hooghiemstra

Annales de l'I.H.P. Probabilités et statistiques (2013)

  • Volume: 49, Issue: 3, page 817-838
  • ISSN: 0246-0203

Abstract

top
We formulate and study a model for inhomogeneous long-range percolation on ℤ d . Each vertex x ∈ ℤ d is assigned a non-negative weight W x , where ( W x ) x ∈ ℤ d are i.i.d. random variables. Conditionally on the weights, and given two parameters α , λ g t ; 0 , the edges are independent and the probability that there is an edge between x and y is given by p x y = 1 - exp { - λ W x W y / | x - y | α } . The parameter λ is the percolation parameter, while α describes the long-range nature of the model. We focus on the degree distribution in the resulting graph, on whether there exists an infinite component and on graph distance between remote pairs of vertices. First, we show that the tail behavior of the degree distribution is related to the tail behavior of the weight distribution. When the tail of the distribution of W x is regularly varying with exponent τ - 1 , then the tail of the degree distribution is regularly varying with exponent γ = α ( τ - 1 ) / d . The parameter γ turns out to be crucial for the behavior of the model. Conditions on the weight distribution and γ are formulated for the existence of a critical value λ c ∈ ( 0 , ∞ ) such that the graph contains an infinite component when λ g t ; λ c and no infinite component when λ l t ; λ c . Furthermore, a phase transition is established for the graph distances between vertices in the infinite component at the point γ = 2 , that is, at the point where the degrees switch from having finite to infinite second moment. The model can be viewed as an interpolation between long-range percolation and models for inhomogeneous random graphs, and we show that the behavior shares the interesting features of both these models.

How to cite

top

Deijfen, Maria, van der Hofstad, Remco, and Hooghiemstra, Gerard. "Scale-free percolation." Annales de l'I.H.P. Probabilités et statistiques 49.3 (2013): 817-838. <http://eudml.org/doc/271988>.

@article{Deijfen2013,
abstract = {We formulate and study a model for inhomogeneous long-range percolation on $\mathbb \{Z\}^\{d\}$. Each vertex $x\in \mathbb \{Z\}^\{d\}$ is assigned a non-negative weight $W_\{x\}$, where $(W_\{x\})_\{x\in \mathbb \{Z\}\}^\{d\}$ are i.i.d. random variables. Conditionally on the weights, and given two parameters $\alpha ,\lambda &gt;0$, the edges are independent and the probability that there is an edge between $x$ and $y$ is given by $p_\{xy\}=1-\exp \lbrace -\lambda W_\{x\}W_\{y\}/|x-y|^\{\alpha \}\rbrace $. The parameter $\lambda $ is the percolation parameter, while $\alpha $ describes the long-range nature of the model. We focus on the degree distribution in the resulting graph, on whether there exists an infinite component and on graph distance between remote pairs of vertices. First, we show that the tail behavior of the degree distribution is related to the tail behavior of the weight distribution. When the tail of the distribution of $W_\{x\}$ is regularly varying with exponent $\tau -1$, then the tail of the degree distribution is regularly varying with exponent $\gamma =\alpha (\tau -1)/d$. The parameter $\gamma $ turns out to be crucial for the behavior of the model. Conditions on the weight distribution and $\gamma $ are formulated for the existence of a critical value $\lambda _\{\mathrm \{c\}\}\in (0,\infty )$ such that the graph contains an infinite component when $\lambda &gt;\lambda _\{\mathrm \{c\}\}$ and no infinite component when $\lambda &lt;\lambda _\{\mathrm \{c\}\}$. Furthermore, a phase transition is established for the graph distances between vertices in the infinite component at the point $\gamma =2$, that is, at the point where the degrees switch from having finite to infinite second moment. The model can be viewed as an interpolation between long-range percolation and models for inhomogeneous random graphs, and we show that the behavior shares the interesting features of both these models.},
author = {Deijfen, Maria, van der Hofstad, Remco, Hooghiemstra, Gerard},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {random graphs; Long-range percolation; percolation in random environment; degree distribution; phase transition; chemical distance; graph distance; long-range percolation},
language = {eng},
number = {3},
pages = {817-838},
publisher = {Gauthier-Villars},
title = {Scale-free percolation},
url = {http://eudml.org/doc/271988},
volume = {49},
year = {2013},
}

TY - JOUR
AU - Deijfen, Maria
AU - van der Hofstad, Remco
AU - Hooghiemstra, Gerard
TI - Scale-free percolation
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2013
PB - Gauthier-Villars
VL - 49
IS - 3
SP - 817
EP - 838
AB - We formulate and study a model for inhomogeneous long-range percolation on $\mathbb {Z}^{d}$. Each vertex $x\in \mathbb {Z}^{d}$ is assigned a non-negative weight $W_{x}$, where $(W_{x})_{x\in \mathbb {Z}}^{d}$ are i.i.d. random variables. Conditionally on the weights, and given two parameters $\alpha ,\lambda &gt;0$, the edges are independent and the probability that there is an edge between $x$ and $y$ is given by $p_{xy}=1-\exp \lbrace -\lambda W_{x}W_{y}/|x-y|^{\alpha }\rbrace $. The parameter $\lambda $ is the percolation parameter, while $\alpha $ describes the long-range nature of the model. We focus on the degree distribution in the resulting graph, on whether there exists an infinite component and on graph distance between remote pairs of vertices. First, we show that the tail behavior of the degree distribution is related to the tail behavior of the weight distribution. When the tail of the distribution of $W_{x}$ is regularly varying with exponent $\tau -1$, then the tail of the degree distribution is regularly varying with exponent $\gamma =\alpha (\tau -1)/d$. The parameter $\gamma $ turns out to be crucial for the behavior of the model. Conditions on the weight distribution and $\gamma $ are formulated for the existence of a critical value $\lambda _{\mathrm {c}}\in (0,\infty )$ such that the graph contains an infinite component when $\lambda &gt;\lambda _{\mathrm {c}}$ and no infinite component when $\lambda &lt;\lambda _{\mathrm {c}}$. Furthermore, a phase transition is established for the graph distances between vertices in the infinite component at the point $\gamma =2$, that is, at the point where the degrees switch from having finite to infinite second moment. The model can be viewed as an interpolation between long-range percolation and models for inhomogeneous random graphs, and we show that the behavior shares the interesting features of both these models.
LA - eng
KW - random graphs; Long-range percolation; percolation in random environment; degree distribution; phase transition; chemical distance; graph distance; long-range percolation
UR - http://eudml.org/doc/271988
ER -

References

top
  1. [1] M. Aizenman and C. M. Newman. Discontinuity of the percolation density in one dimensional 1 / | x - y | 2 percolation models. Comm. Math. Phys.107 (1986) 611–647. Zbl0613.60097MR868738
  2. [2] D. Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab.25 (1997) 812–854. Zbl0877.60010MR1434128
  3. [3] I. Benjamini, H. Kesten, Y. Peres and O. Schramm. Geometry of the uniform spanning forest: Transitions in diameters 4, 8, 12, … . Ann. of Math. 160 (2004) 465–491. Zbl1071.60006MR2123930
  4. [4] N. Berger. Transience, recurrence and critical behavior for long-range percolation. Comm. Math. Phys. 226 (3) (2002) 531–558. Zbl0991.82017MR1896880
  5. [5] N. Berger. A lower bound for chemical distances in sparse long-range percolation models. Preprint, 2004. Available at arXiv:math/0409021v1. 
  6. [6] S. Bhamidi, R. van der Hofstad and J. van Leeuwaarden. Novel scaling limits for critical inhomogeneous random graphs. Preprint, 2009. Zbl1257.05157MR3050505
  7. [7] S. Bhamidi, R. van der Hofstad and J. van Leeuwaarden. Scaling limits for critical inhomogeneous random graphs with finite third moments. Electron. J. Probab.15 (2010) 1682–1702. Zbl1228.60018MR2735378
  8. [8] N. H. Bingham, C. M. Goldie and J. L. Teugels. Regular Variation. Encyclopedia of Mathematics and Its Applications 27. Cambridge Univ. Press, Cambridge, 1987. Zbl0617.26001MR898871
  9. [9] M. Biskup. On the scaling of the chemical distance in long range percolation models. Ann. Probab.32 (2004) 2933–2977. Zbl1072.60084MR2094435
  10. [10] B. Bollobás and O. Riordan. Percolation. Cambridge Univ. Press, New York, 2006. Zbl1118.60001MR2283880
  11. [11] B. Bollobás, O. Riordan and S. Janson. The phase transition in inhomogeneous random graphs. Rand. Struct. Alg.31 (2007) 3–122. Zbl1123.05083MR2337396
  12. [12] T. Britton, M. Deijfen and A. Martin-Löf. Generating simple random graphs with prescribed degree distribution. J. Stat. Phys.124 (2006) 1377–1397. Zbl1106.05086MR2266448
  13. [13] F. Chung and L. Lu. The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA99 (2002) 15879–15882. Zbl1064.05137MR1944974
  14. [14] F. Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Ann. Comb.6 (2002) 125–145. Zbl1009.05124MR1955514
  15. [15] D. Coppersmith, D. Gamarnik and M. Sviridenko. The diameter of a long-range percolation graph. Rand. Struct. Alg.21 (2002) 1–13. Zbl1011.60086MR1913075
  16. [16] S. Dommers, R. van der Hofstad and G. Hooghiemstra. Diameters in preferential attachment graphs. J. Stat. Phys.139 (2010) 72–107. Zbl1191.82020MR2602984
  17. [17] W. Feller. An Introduction to Probability Theory and Its Applications, Vol. 2, 2nd edition. Wiley, New York, 1971. Zbl0039.13201MR270403
  18. [18] A. Gandolfi, M. S. Keane and C. M. Newman. Uniqueness of the infinite component in a random graph with applications to percolation and spin glasses. Probab. Theory Related Fields92 (1992) 511–527. Zbl0767.60098MR1169017
  19. [19] G. Grimmett. Percolation, 2nd edition. Springer, Berlin, 1999. Zbl0926.60004MR1707339
  20. [20] H. Hatami and M. Molloy. The scaling window for a random graph with a given degree sequence. Preprint, 2009. Zbl1247.05218MR2809753
  21. [21] M. Heydenreich, R. van der Hofstad and A. Sakai. Mean-field behavior for long- and finite range ising model, percolation and self-avoiding walk. J. Stat. Phys. 132 (5) (2008) 1001–1049. Zbl1152.82007MR2430773
  22. [22] S. Janson. Asymptotic equivalence and contiguity of some random graphs. Rand. Struct. Alg. 36 (1) 201026–45. Zbl1209.05225MR2591045
  23. [23] T. M. Liggett, R. H. Schonmann and A. M. Stacey. Domination by product measure. Ann. Probab.25 (1997) 71–95. Zbl0882.60046MR1428500
  24. [24] R. Meester and R. Roy. Continuum Percolation. Cambridge Univ. Press, Cambridge, 1996. Zbl1146.60076MR1409145
  25. [25] C. M. Newman and L. S. Schulman. One-dimensional 1 / | j - i | s percolation models: The existence of a transition for s ≤ 2 . Comm. Math. Phys.104 (1986) 547–571. Zbl0604.60097MR841669
  26. [26] I. Norros and H. Reittu. On a conditionally Poissonian graph process. Adv. in Appl. Probab.38 (2006) 59–75. Zbl1096.05047MR2213964
  27. [27] L. S. Schulman. Long range percolation in one dimension. J. Phys. A 16 (1983) L639–L641. MR701466
  28. [28] S. Smirnov. Critical percolation in the plane: Conformal invariance, Cardy’s formula, scaling limits. C. R. Acad. Sci. Paris Sér. I Math. 333 (3) (2001) 239–244. Zbl0985.60090MR1851632
  29. [29] T. S. Turova. Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1. Preprint, 2009. Zbl1278.05227MR3124693
  30. [30] J. E. Yukich. Ultra-small scale-free geometric networks. J. Appl. Probab.43 (2006) 665–677. Zbl1120.60095MR2274791
  31. [31] R. van der Hofstad. Critical behavior in inhomogeneous random graphs. Preprint, 2009. Zbl1269.05101MR3068034
  32. [32] R. van der Hofstad, G. Hooghiemstra and P. Van Mieghem. Distances in random graphs with finite variance degrees. Rand. Struct. Alg.26 (2005) 76–123. Zbl1074.05083MR2150017
  33. [33] R. van der Hofstad, G. Hooghiemstra and D. Znamenski. Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab.12 (2007) 703–766. Zbl1126.05090MR2318408

NotesEmbed ?

top

You must be logged in to post comments.