Scale-free percolation

Deijfen, Maria ; van der Hofstad, Remco ; Hooghiemstra, Gerard

Annales de l'I.H.P. Probabilités et statistiques, Tome 49 (2013), p. 817-838 / Harvested from Numdam

Résumé

Nous définissons et étudions un modèle de percolation inhomogènes à longue portée sur $\mathbb {Z}^{d}$. A chaque site $x\in \mathbb {Z}^{d}$ est assigné un poids positif $W_{x}$, où les $(W_{x})_{x\in \mathbb {Z}^{d}}$ sont des variables aléatoires indépendantes et identiquement distribuées. Conditionnellement aux poids et étant donnés deux paramètres $\alpha ,\lambda >0$, les arêtes sont indépendantes et la probabilité qu’il existe un lien entre $x$ et $y$ est $p_{xy}=1-\exp \lbrace -\lambda W_{x}W_{y}/|x-y|^{\alpha }\rbrace $. Le paramètre $\lambda $ est le paramètre de percolation tandis que $\alpha $ caractérise la portée des interactions. Nous étudierons la distribution des degrés dans le graphe résultant et l’existence éventuelle d’une composante infinie ainsi que la distance de graphe entre deux sites éloignés. Nous montrons d’abord que la queue de la distribution des degrés est liée à la queue de la distribution des poids. Quand la queue de la distribution de $W_{x}$ est à variation régulière d’indice $\tau -1$, alors la queue de la distribution des degrés est à variation régulière d’indice $\gamma =\alpha (\tau -1)/d$. Le paramètre $\gamma $ s’avère crucial pour décrire le modèle. Des conditions sur la distribution des poids et de $\gamma $ sont formulées pour l’existence d’une valeur critique $\lambda _{\mathrm {c}}\in (0,\infty )$ telle que le graphe contienne une composante infinie quand $\lambda >\lambda _{\mathrm {c}}$ et aucune composante infinie quand $\lambda <\lambda _{\mathrm {c}}$. De plus, une transition de phase est établie pour la distance dans le graphe de la composante infinie au point $\gamma =2$, c’est à dire au point où les degrés n’ont plus de second moment fini. Notre modèle peut être vu comme une interpolation entre la percolation à longue portée et des modèles de graphes aléatoires inhomogènes. Nous montrons qu’il possède les caractéristiques des deux modèles précédents.

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 >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 >\lambda _{\mathrm {c}}$ and no infinite component when $\lambda <\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.

Détail

Publié le : 2013-01-01

MR 3112435 | Zbl 1274.60290

DOI : https://doi.org/10.1214/12-AIHP480
Classification:  60K35,  05C80

Bibliographie

[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. | MR 868738 | Zbl 0613.60097

[2] D. Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 (1997) 812-854. | MR 1434128 | Zbl 0877.60010

[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. | MR 2123930 | Zbl 1071.60006

[4] N. Berger. Transience, recurrence and critical behavior for long-range percolation. Comm. Math. Phys. 226 (3) (2002) 531-558. | MR 1896880 | Zbl 0991.82017

[5] N. Berger. A lower bound for chemical distances in sparse long-range percolation models. Preprint, 2004. Available at arXiv:math/0409021v1.

[6] S. Bhamidi, R. Van Der Hofstad and J. Van Leeuwaarden. Novel scaling limits for critical inhomogeneous random graphs. Preprint, 2009. | MR 3050505 | Zbl 1257.05157

[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. | MR 2735378 | Zbl 1228.60018

[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. | MR 898871 | Zbl 0617.26001

[9] M. Biskup. On the scaling of the chemical distance in long range percolation models. Ann. Probab. 32 (2004) 2933-2977. | MR 2094435 | Zbl 1072.60084

[10] B. Bollobás and O. Riordan. Percolation. Cambridge Univ. Press, New York, 2006. | MR 2283880 | Zbl 1118.60001

[11] B. Bollobás, O. Riordan and S. Janson. The phase transition in inhomogeneous random graphs. Rand. Struct. Alg. 31 (2007) 3-122. | MR 2337396 | Zbl 1123.05083

[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. | MR 2266448 | Zbl 1106.05086

[13] F. Chung and L. Lu. The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA 99 (2002) 15879-15882. | MR 1944974 | Zbl 1064.05137

[14] F. Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Ann. Comb. 6 (2002) 125-145. | MR 1955514 | Zbl 1009.05124

[15] D. Coppersmith, D. Gamarnik and M. Sviridenko. The diameter of a long-range percolation graph. Rand. Struct. Alg. 21 (2002) 1-13. | MR 1913075 | Zbl 1011.60086

[16] S. Dommers, R. Van Der Hofstad and G. Hooghiemstra. Diameters in preferential attachment graphs. J. Stat. Phys. 139 (2010) 72-107. | MR 2602984 | Zbl 1191.82020

[17] W. Feller. An Introduction to Probability Theory and Its Applications, Vol. 2, 2nd edition. Wiley, New York, 1971. | MR 270403 | Zbl 0039.13201

[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 Fields 92 (1992) 511-527. | MR 1169017 | Zbl 0767.60098

[19] G. Grimmett. Percolation, 2nd edition. Springer, Berlin, 1999. | MR 1707339

[20] H. Hatami and M. Molloy. The scaling window for a random graph with a given degree sequence. Preprint, 2009. | MR 2809753 | Zbl 1247.05218

[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. | MR 2430773 | Zbl 1152.82007

[22] S. Janson. Asymptotic equivalence and contiguity of some random graphs. Rand. Struct. Alg. 36 (1) 2010 26-45. | MR 2591045 | Zbl 1209.05225

[23] T. M. Liggett, R. H. Schonmann and A. M. Stacey. Domination by product measure. Ann. Probab. 25 (1997) 71-95. | MR 1428500 | Zbl 0882.60046

[24] R. Meester and R. Roy. Continuum Percolation. Cambridge Univ. Press, Cambridge, 1996. | MR 1409145 | Zbl 1146.60076

[25] C. M. Newman and L. S. Schulman. One-dimensional $1/|j-i|^{s}$ percolation models: The existence of a transition for $s\le 2$. Comm. Math. Phys. 104 (1986) 547-571. | MR 841669 | Zbl 0604.60097

[26] I. Norros and H. Reittu. On a conditionally Poissonian graph process. Adv. in Appl. Probab. 38 (2006) 59-75. | MR 2213964 | Zbl 1096.05047

[27] L. S. Schulman. Long range percolation in one dimension. J. Phys. A 16 (1983) L639-L641. | MR 701466

[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. | MR 1851632 | Zbl 0985.60090

[29] T. S. Turova. Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1. Preprint, 2009. | MR 3124693 | Zbl 1278.05227

[30] J. E. Yukich. Ultra-small scale-free geometric networks. J. Appl. Probab. 43 (2006) 665-677. | MR 2274791 | Zbl 1120.60095

[31] R. Van Der Hofstad. Critical behavior in inhomogeneous random graphs. Preprint, 2009. | MR 3068034 | Zbl 1269.05101

[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. | MR 2150017 | Zbl 1074.05083

[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. | MR 2318408 | Zbl 1126.05090