Geodesic
Number of maximal rooted trees in uniform attachment model via stochastic approximation
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2022), pp. 27-34 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We study the asymptotic behavior of the number of maximal trees in a uniform attachment model. In our model, we consider a sequence of graphs built by the following recursive rule. We start with the complete graph on $m+1$ vertices, $m>1$. Then on the $n+1$ step, we add vertex $n+1$ and draw $m$ edges from it to different vertices, chosen uniformly from $1,\ldots,n$. We prove the convergence speed for the number of maximal trees in such a model using the stochastic approximation technique.
Keywords: random graphs, uniform attachment, stochastic approximation. 
@article{VTPMK_2022_3_a1,
     author = {Yu. A. Malyshkin},
     title = {Number of maximal rooted trees in uniform attachment model via stochastic approximation},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {27--34},
     year = {2022},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2022_3_a1/}
}
TY  - JOUR
AU  - Yu. A. Malyshkin
TI  - Number of maximal rooted trees in uniform attachment model via stochastic approximation
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2022
SP  - 27
EP  - 34
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2022_3_a1/
LA  - ru
ID  - VTPMK_2022_3_a1
ER  - 
%0 Journal Article
%A Yu. A. Malyshkin
%T Number of maximal rooted trees in uniform attachment model via stochastic approximation
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2022
%P 27-34
%N 3
%U http://geodesic.mathdoc.fr/item/VTPMK_2022_3_a1/
%G ru
%F VTPMK_2022_3_a1
Yu. A. Malyshkin. Number of maximal rooted trees in uniform attachment model via stochastic approximation. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2022), pp. 27-34. http://geodesic.mathdoc.fr/item/VTPMK_2022_3_a1/

[1] Chen H. F., Stochastic Approximation and Its Applications, v. 64, Nonconvex Optimization and its Applications, Springer, New York, 2002, 360 pp. | DOI

[2] Frieze A., Karonski M., Introduction to random graphs, Cambridge University Press, 2016, 478 pp.

[3] Garavaglia A., Preferential attachment models for dynamic networks, Technische Universiteit Eindhoven, 2019, 305 pp.

[4] Malyshkin Y. A., Zhukovskii M. E., “MSO 0-1 law for recursive random trees”, Statistics and Probability Letters, 173 (2021), 109061

[5] Malyshkin Y. A., Zhukovskii M. E., “$\gamma$-variable first-order logic of uniform attachment random graphs”, Discrete Mathematics, 345:5 (2022), 112802

[6] Pemantle R., “A survey of random processes with reinforcement”, Probability Surveys, 4 (2007), 1–79