Theory of Probability and Mathematical Statistics

Number of maximal rooted trees in preferential attachment model via stochastic approximation

Yu. A. Malyshkin

Tver State University, Tver

Abstract: 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.

UDC: 519.17, 519.21

Received: 24.11.2022
Revised: 21.06.2023

Language: English

DOI: 10.26456/vtpmk688

Bibliographic databases:

•