Geodesic
Number of maximal rooted trees in preferential attachment model via stochastic approximation
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 2 (2023), pp. 28-36 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 the preferential 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 from $1,\ldots,n$, chosen with probabilities proportional to their degrees plus some positive parameter $\beta$. We prove the convergence speed for the number of maximal trees in such a model using the stochastic approximation technique.
Keywords: random graphs, preferential attachment, stochastic approximation. 
@article{VTPMK_2023_2_a2,
     author = {Yu. A. Malyshkin},
     title = {Number of maximal rooted trees in preferential attachment model via stochastic approximation},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {28--36},
     year = {2023},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2023_2_a2/}
}
TY  - JOUR
AU  - Yu. A. Malyshkin
TI  - Number of maximal rooted trees in preferential attachment model via stochastic approximation
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2023
SP  - 28
EP  - 36
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2023_2_a2/
LA  - en
ID  - VTPMK_2023_2_a2
ER  - 
%0 Journal Article
%A Yu. A. Malyshkin
%T Number of maximal rooted trees in preferential attachment model via stochastic approximation
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2023
%P 28-36
%N 2
%U http://geodesic.mathdoc.fr/item/VTPMK_2023_2_a2/
%G en
%F VTPMK_2023_2_a2
Yu. A. Malyshkin. Number of maximal rooted trees in preferential attachment model via stochastic approximation. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 2 (2023), pp. 28-36. http://geodesic.mathdoc.fr/item/VTPMK_2023_2_a2/

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

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

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

[4] Malyshkin Y. A., “$\gamma$-variable first-order logic of preferential attachment random graphs”, Discrete Applied Mathematics, 314 (2022), 223–227 | DOI | MR | Zbl

[5] Malyshkin Y. A., “Number of maximal rooted trees in uniform attachment model via stochastic approximation”, Vestnik TvGU. Seriya: Prikladnaya Matematika, 3 (2022), 27–34

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

[7] Malyshkin Y. A., Zhukovskii M. E., Logical convergence laws via stochastic approximation and Markov processes, Preprint at https://arxiv.org/abs/2210.13437, 2022

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