Scaling limits and influence of the seed graph in preferential attachment trees
[Limites d’échelle et ontogenèse des arbres construits par attachement préférentiel]
Curien, Nicolas1 ; Duquesne, Thomas2 ; Kortchemski, Igor3 ; Manolescu, Ioan4
1 Département de mathématiques, Université Paris-Sud Orsay Bâtiment 425, 91405 Orsay, France
2 LPMA, Université Pierre et Marie Curie (Paris 6) Case courrier 188, 4 place Jussieu, 75252 Paris Cedex 05, France
3 Département de Mathématiques et Applications, École Normale Supérieure 45 rue d’Ulm, 75230 Paris Cedex 05, France
4 Département de Mathématiques, Université de Genève 2-4 rue du Lièvre, Case postale 64, 1211 Genève 4, Suisse
Journal de l’École polytechnique - Mathématiques, Tome 2 (2015), pp. 1-34.

Nous nous intéressons au comportement asymptotique d’arbres aléatoires construits par attachement préférentiel linéaire, qui sont aussi connus dans la littérature sous le nom d’arbres de Barabási-Albert ou encore arbres plans récursifs. Nous validons une conjecture de Bubeck, Mossel & Rácz relative à l’influence de l’arbre initial sur le comportement asymptotique de ces arbres. Séparément, nous étudions la structure géométrique des sommets de grand degré dans la version planaire des arbres de Barabási-Albert en considérant leurs « arbres à boucles ». Lorsque le nombre de sommets croît, nous prouvons que ces arbres à boucles, convenablement mis à l’échelle, convergent au sens de Gromov-Hausdorff vers un espace métrique compact aléatoire, que nous appelons « l’arbre à boucles brownien ». Ce dernier est construit comme un espace quotient de l’arbre continu brownien d’Aldous, et nous prouvons que sa dimension de Hausdorff vaut 2 presque sûrement.

We are interested in the asymptotics of random trees built by linear preferential attachment, also known in the literature as Barabási–Albert trees or plane-oriented recursive trees. We first prove a conjecture of Bubeck, Mossel & Rácz [9] concerning the influence of the seed graph on the asymptotic behavior of such trees. Separately we study the geometric structure of nodes of large degrees in a plane version of Barabási–Albert trees via their associated looptrees. As the number of nodes grows, we show that these looptrees, appropriately rescaled, converge in the Gromov–Hausdorff sense towards a random compact metric space which we call the Brownian looptree. The latter is constructed as a quotient space of Aldous’ Brownian Continuum Random Tree and is shown to have almost sure Hausdorff dimension 2.

DOI : 10.5802/jep.15
Classification : 05C80, 60J80, 05C05, 60G42
Keywords: Preferential attachment model, Brownian tree, Looptree, Poisson boundary
Mot clés : Modèle d’attachement préférentiel, arbre brownien, arbre à boucles, bord de Poisson
Curien, Nicolas 1 ; Duquesne, Thomas 2 ; Kortchemski, Igor 3 ; Manolescu, Ioan 4

1 Département de mathématiques, Université Paris-Sud Orsay Bâtiment 425, 91405 Orsay, France
2 LPMA, Université Pierre et Marie Curie (Paris 6) Case courrier 188, 4 place Jussieu, 75252 Paris Cedex 05, France
3 Département de Mathématiques et Applications, École Normale Supérieure 45 rue d’Ulm, 75230 Paris Cedex 05, France
4 Département de Mathématiques, Université de Genève 2-4 rue du Lièvre, Case postale 64, 1211 Genève 4, Suisse 
@article{JEP_2015__2__1_0,
     author = {Curien, Nicolas and Duquesne, Thomas and Kortchemski, Igor and Manolescu, Ioan},
     title = {Scaling limits and influence of the seed graph in preferential attachment trees},
     journal = {Journal de l{\textquoteright}\'Ecole polytechnique - Math\'ematiques},
     pages = {1--34},
     publisher = {Ecole polytechnique},
     volume = {2},
     year = {2015},
     doi = {10.5802/jep.15},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/jep.15/}
}
TY  - JOUR
AU  - Curien, Nicolas
AU  - Duquesne, Thomas
AU  - Kortchemski, Igor
AU  - Manolescu, Ioan
TI  - Scaling limits and influence of the seed graph in preferential attachment trees
JO  - Journal de l’École polytechnique - Mathématiques
PY  - 2015
SP  - 1
EP  - 34
VL  - 2
PB  - Ecole polytechnique
UR  - https://www.numdam.org/articles/10.5802/jep.15/
DO  - 10.5802/jep.15
LA  - en
ID  - JEP_2015__2__1_0
ER  - 
%0 Journal Article
%A Curien, Nicolas
%A Duquesne, Thomas
%A Kortchemski, Igor
%A Manolescu, Ioan
%T Scaling limits and influence of the seed graph in preferential attachment trees
%J Journal de l’École polytechnique - Mathématiques
%D 2015
%P 1-34
%V 2
%I Ecole polytechnique
%U https://www.numdam.org/articles/10.5802/jep.15/
%R 10.5802/jep.15
%G en
%F JEP_2015__2__1_0
Curien, Nicolas; Duquesne, Thomas; Kortchemski, Igor; Manolescu, Ioan. Scaling limits and influence of the seed graph in preferential attachment trees. Journal de l’École polytechnique - Mathématiques, Tome 2 (2015), pp. 1-34. doi : 10.5802/jep.15. https://www.numdam.org/articles/10.5802/jep.15/

[1] Addario-Berry, L.; Broutin, N.; Goldschmidt, C. The continuum limit of critical random graphs, Probab. Theory Related Fields, Volume 152 (2012) no. 3-4, pp. 367-406 | DOI | MR | Zbl

[2] Aldous, D. The continuum random tree. I, Ann. Probab., Volume 19 (1991) no. 1, pp. 1-28 http://www.jstor.org/stable/2244250 | MR | Zbl

[3] Aldous, D. Recursive self-similarity for random trees, random triangulations and Brownian excursion, Ann. Probab., Volume 22 (1994) no. 2, pp. 527-545 http://www.jstor.org/stable/2244884 | MR | Zbl

[4] Athreya, K. B. On a characteristic property of Pólya’s urn, Studia Sci. Math. Hungar., Volume 4 (1969), pp. 31-35 | MR | Zbl

[5] Barabási, A.-L.; Albert, R. Emergence of scaling in random networks, Science, Volume 286 (1999) no. 5439, pp. 509-512 | DOI | MR | Zbl

[6] Berger, N.; Borgs, Ch.; Chayes, J. T.; Saberi, A. Asymptotic behavior and distributional limits of preferential attachment graphs, Ann. Probab., Volume 42 (2014) no. 1, pp. 1-40 | DOI | MR | Zbl

[7] Bollobás, B.; Riordan, O.; Spencer, J.; Tusnády, G. The degree sequence of a scale-free random graph process, Random Structures Algorithms, Volume 18 (2001) no. 3, pp. 279-290 | DOI | MR | Zbl

[8] Bubeck, S.; Mossel, E.; Rácz, M. Z. On the influence of the seed graph in the preferential attachment model (2014) (arXiv:1401.4849v2)

[9] Bubeck, S.; Mossel, E.; Rácz, M. Z. On the influence of the seed graph in the preferential attachment model (2014) (arXiv:1401.4849v3)

[10] Burago, D.; Burago, Y.; Ivanov, S. A course in metric geometry, Graduate Studies in Mathematics, 33, American Mathematical Society, Providence, RI, 2001, pp. xiv+415 | MR | Zbl

[11] Chauvin, B.; Mailler, C.; Pouyanne, N. Smoothing equations for large Pólya urns. (2013) (to appear in Journal of Theoretical Probability, arXiv:1302.1412)

[12] Curien, N.; Haas, B. The stable trees are nested, Probab. Theory Related Fields, Volume 157 (2013) no. 3-4, pp. 847-883 | DOI | MR | Zbl

[13] Curien, N.; Kortchemski, I. Random stable looptrees (2013) (arXiv:1304.1044)

[14] Curien, N.; Kortchemski, I. Percolation on random triangulations and stable looptrees (2013) (arXiv:1307.6818)

[15] Dereich, S.; Mörters, P. Random networks with sublinear preferential attachment: the giant component, Ann. Probab., Volume 41 (2013) no. 1, pp. 329-384 | DOI | MR | Zbl

[16] Evans, S. N. Probability and real trees, Lect. Notes in Math., 1920, Springer, Berlin, 2008, pp. xii+193 (Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6–23, 2005) | DOI | MR | Zbl

[17] Ford, D. J. Probabilities on cladograms: Introduction to the alpha model (2005) (arXiv:math/0511246v1) | MR

[18] Haas, B.; Miermont, G. Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees, Ann. Probab., Volume 40 (2012) no. 6, pp. 2589-2666 | DOI | MR | Zbl

[19] van der Hofstad, R. Random graphs and complex networks (2013) (in preparation, http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf)

[20] Le Gall, J.-F. Random trees and applications, Probab. Surv., Volume 2 (2005), pp. 245-311 | DOI | MR | Zbl

[21] Le Gall, J.-F. Random geometry on the sphere, Proceedings of ICM 2014, Seoul (2014) (to appear, arXiv:1403.7943)

[22] Mattila, P. Geometry of sets and measures in Euclidean spaces: Fractals and rectifiability, Cambridge Studies in Advanced Mathematics, 44, Cambridge University Press, Cambridge, 1995, pp. xii+343 | DOI | MR | Zbl

[23] Miermont, G. Tessellations of random maps of arbitrary genus, Ann. Sci. École Norm. Sup. (4), Volume 42 (2009) no. 5, pp. 725-781 | Numdam | MR | Zbl

[24] Móri, T. F. On random trees, Studia Sci. Math. Hungar., Volume 39 (2002) no. 1-2, pp. 143-155 | DOI | MR | Zbl

[25] Móri, T. F. The maximum degree of the Barabási-Albert random tree, Combin. Probab. Comput., Volume 14 (2005) no. 3, pp. 339-348 | DOI | MR | Zbl

[26] Peköz, E. A.; Röllin, A.; Ross, N. Joint degree distributions of preferential attachment random graphs (2014) (arXiv:1402.4686)

[27] Pitman, J. Combinatorial stochastic processes, Lect. Notes in Math., 1875, Springer-Verlag, Berlin, 2006, pp. x+256 (Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002) | MR | Zbl

[28] Rémy, J.-L. Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire, RAIRO Inform. Théor., Volume 19 (1985) no. 2, pp. 179-195 | Numdam | MR | Zbl

[29] Szymański, J. On a nonuniform random recursive tree, Random graphs ’85 (Poznań, 1985) (North-Holland Math. Stud.), Volume 144, North-Holland, Amsterdam, 1987, pp. 297-306 | MR | Zbl

[30] Woess, W. Random walks on infinite graphs and groups, Cambridge Tracts in Mathematics, 138, Cambridge University Press, Cambridge, 2000, pp. xii+334 | DOI | MR | Zbl

  • Ben-Hamou, Anna; Velona, Vasiliki Inference in balanced community modulated recursive trees, Bernoulli, Volume 31 (2025) no. 1 | DOI:10.3150/24-bej1735
  • Crane, Harry; Xu, Min Root and community inference on the latent growth process of a network, Journal of the Royal Statistical Society Series B: Statistical Methodology, Volume 86 (2024) no. 4, p. 825 | DOI:10.1093/jrsssb/qkad102
  • Rampazzo, Marco New counterexamples to the birational Torelli theorem for Calabi–Yau manifolds, Proceedings of the American Mathematical Society (2024) | DOI:10.1090/proc/16745
  • Haas, Bénédicte Tail asymptotics for extinction times of self-similar fragmentations, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Volume 59 (2023) no. 3 | DOI:10.1214/22-aihp1306
  • Briend, Simon; Calvillo, Francisco; Lugosi, Gábor Archaeology of random recursive dags and Cooper-Frieze random networks, Combinatorics, Probability and Computing, Volume 32 (2023) no. 6, p. 859 | DOI:10.1017/s0963548323000184
  • Banerjee, Sayan; Huang, Xiangying Degree centrality and root finding in growing random networks, Electronic Journal of Probability, Volume 28 (2023) no. none | DOI:10.1214/23-ejp930
  • Banerjee, Sayan; Bhamidi, Shankar; Carmichael, Iain Fluctuation bounds for continuous time branching processes and evolution of growing trees with a change point, The Annals of Applied Probability, Volume 33 (2023) no. 4 | DOI:10.1214/22-aap1881
  • Ged, François G. Intrinsic area near the origin for self-similar growth-fragmentations and related random surfaces, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Volume 58 (2022) no. 2 | DOI:10.1214/21-aihp1185
  • Sénizergues, Delphin Growing random graphs with a preferential attachment structure, Latin American Journal of Probability and Mathematical Statistics, Volume 19 (2022) no. 1, p. 259 | DOI:10.30757/alea.v19-11
  • Brandenberger, Anna M.; Devroye, Luc; Goh, Marcel K. Root estimation in Galton–Watson trees, Random Structures Algorithms, Volume 61 (2022) no. 3, p. 520 | DOI:10.1002/rsa.21072
  • Addario-Berry, Louigi; Devroye, Luc; Lugosi, Gábor; Velona, Vasiliki Broadcasting on random recursive trees, The Annals of Applied Probability, Volume 32 (2022) no. 1 | DOI:10.1214/21-aap1686
  • Rácz, Miklós Z.; Sridhar, Anirudh Correlated randomly growing graphs, The Annals of Applied Probability, Volume 32 (2022) no. 2 | DOI:10.1214/21-aap1703
  • Banerjee, Sayan; Bhamidi, Shankar Root finding algorithms and persistence of Jordan centrality in growing random trees, The Annals of Applied Probability, Volume 32 (2022) no. 3 | DOI:10.1214/21-aap1731
  • Archer, Eleanor Brownian motion on stable looptrees, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Volume 57 (2021) no. 2 | DOI:10.1214/20-aihp1103
  • Banerjee, Sayan; Bhamidi, Shankar Persistence of hubs in growing random networks, Probability Theory and Related Fields, Volume 180 (2021) no. 3-4, p. 891 | DOI:10.1007/s00440-021-01066-0
  • Miller, Jason; Sheffield, Scott Liouville quantum gravity and the Brownian map II: Geodesics and continuity of the embedding, The Annals of Probability, Volume 49 (2021) no. 6 | DOI:10.1214/21-aop1506
  • Corlin Marchand, David; Manolescu, Ioan Influence of the seed in affine preferential attachment trees, Bernoulli, Volume 26 (2020) no. 3 | DOI:10.3150/19-bej1152
  • Archer, Eleanor Infinite stable looptrees, Electronic Journal of Probability, Volume 25 (2020) no. none | DOI:10.1214/20-ejp413
  • Lugosi, Gábor; Pereira, Alan S. Finding the seed of uniform attachment trees, Electronic Journal of Probability, Volume 24 (2019) no. none | DOI:10.1214/19-ejp268
  • Sénizergues, Delphin Random gluing of metric spaces, The Annals of Probability, Volume 47 (2019) no. 6 | DOI:10.1214/19-aop1348
  • Bhamidi, Shankar; Jin, Jimmy; Nobel, Andrew Change point detection in network models: Preferential attachment and long range dependence, The Annals of Applied Probability, Volume 28 (2018) no. 1 | DOI:10.1214/17-aap1297
  • Haas, Bénédicte Scaling Limits of Markov-Branching Trees and Applications, XII Symposium of Probability and Stochastic Processes, Volume 73 (2018), p. 3 | DOI:10.1007/978-3-319-77643-9_1
  • Peköz, Erol; Röllin, Adrian; Ross, Nathan Joint degree distributions of preferential attachment random graphs, Advances in Applied Probability, Volume 49 (2017) no. 2, p. 368 | DOI:10.1017/apr.2017.5
  • Bubeck, Sébastien; Eldan, Ronen; Mossel, Elchanan; Rácz, Miklós Z. From trees to seeds: On the inference of the seed from large trees in the uniform attachment model, Bernoulli, Volume 23 (2017) no. 4A | DOI:10.3150/16-bej831
  • Bubeck, Sébastien; Devroye, Luc; Lugosi, Gábor Finding Adam in random growing trees, Random Structures Algorithms, Volume 50 (2017) no. 2, p. 158 | DOI:10.1002/rsa.20649
  • Rácz, Miklós Z.; Bubeck, Sébastien Basic models and questions in statistical network analysis, Statistics Surveys, Volume 11 (2017) no. none | DOI:10.1214/17-ss117

Cité par 26 documents. Sources : Crossref