Email this article The maximum tree of a random forest in the configuration graph
- Authors: Pavlov Y.L.1
-
Affiliations:
- Institute of Applied Mathematical Research of the Karelian Research Centre RAS
- Issue: Vol 212, No 9 (2021)
- Pages: 146-163
- Section: Articles
- URL: https://journal-vniispk.ru/0368-8666/article/view/133409
- DOI: https://doi.org/10.4213/sm9481
- ID: 133409
Cite item
Open Access
Access granted
Subscription Access
Abstract
Galton-Watson random forests with a given number of root trees and a known number of nonroot vertices are investigated. The distribution of the number of direct offspring of each particle in the forest-generating process is assumed to have infinite variance. Branching processes of this kind are used successfully to study configuration graphs aimed at simulating the structure and development dynamics of complex communication networks, in particular the internet. The known relationship between configuration graphs and random forests reflects the local tree structure of simulated networks. Limit theorems are proved for the maximum size of a tree in a random forest in all basic zones where the number of trees and the number of vertices tend to infinity. Bibliography: 14 titles.
Keywords
About the authors
Yurii Leonidovich Pavlov
Institute of Applied Mathematical Research of the Karelian Research Centre RAS
Email: pavlov@krc.karelia.ru
Doctor of physico-mathematical sciences, Professor
References
- Ю. Л. Павлов, “Условные конфигурационные графы со случайным параметром степенного распределения степеней”, Матем. сб., 209:2 (2018), 120–137
- B. Bollobas, “A probabilistic proof of an asymptotic formula for the number of labelled regular graphs”, European J. Combin., 1:4 (1980), 311–316
- R. van der Hofstad, Random graphs and complex networks, v. 1, Camb. Ser. Stat. Probab. Math., 43, Cambridge Univ. Press, Cambridge, 2017, xvi+321 pp.
- R. Hofstad, Random graphs and complex networks, v. 2, Camb. Ser. Stat. Probab. Math., Cambridge Univ. Press, Cambridge (to appear)
- H. Reittu, I. Norros, “On the power-law random graph model of massive data networks”, Performance Evaluation, 55:1-2 (2004), 3–23
- Ю. Л. Павлов, Случайные леса, КарНЦ РАН, Петрозаводск, 1996, 256 с.
- Н. И. Казимиров, Ю. Л. Павлов, “Одно замечание о лесах Гальтона–Ватсона”, Дискрет. матем., 12:1 (2000), 47–59
- В. М. Золотарев, Одномерные устойчивые распределения, Наука, М., 1983, 304 с.
- Ю. Л. Павлов, “Предельные распределения числа деревьев заданного объема в случайном лесе”, Дискрет. матем., 8:2 (1996), 31–47
- В. Ф. Колчин, Случайные отображения, Наука, М., 1984, 207 с.
- В. Феллер, Введение в теорию вероятностей и ее приложения, т. 2, Мир, М., 1984, 752 с.
- И. А. Ибрагимов, Ю. В. Линник, Независимые и стационарно связанные величины, Наука, М., 1965, 524 с.
- Г. Бэйтмен, А. Эрдейи, Высшие трансцендентные функции. Функции Бесселя, функции параболического цилиндра, ортогональные многочлены, Наука, М., 1966, 295 с.
- А. Б. Мухин, “Локальные предельные теоремы для решетчатых случайных величин”, Теория вероятн. и ее примен., 36:4 (1991), 660–674
Supplementary files
