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:
random forest, configuration graph, tree size, limit theorems.
This research was carried out within the framework of the state assignment of the Ministry of Science and Higher Education of the Russian Federation (agreement no. 075-03-2020-522).
\Bibitem{Pav21}
\by Yu.~L.~Pavlov
\paper The maximum tree of a~random forest in the configuration graph
\jour Sb. Math.
\yr 2021
\vol 212
\issue 9
\pages 1329--1346
\mathnet{http://mi.mathnet.ru/eng/sm9481}
\crossref{https://doi.org/10.1070/SM9481}
\zmath{https://zbmath.org/?q=an:1487.60016}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2021SbMat.212.1329P}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000718596400001}
\elib{https://elibrary.ru/item.asp?id=47540482}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85120772460}
Linking options:
https://www.mathnet.ru/eng/sm9481
https://doi.org/10.1070/SM9481
https://www.mathnet.ru/eng/sm/v212/i9/p146
This publication is cited in the following 10 articles:
Yu. L. Pavlov, “Ob ob'emakh derevev lesa Galtona – Vatsona v promezhutochnom sluchae”, Diskret. matem., 37:1 (2025), 39–51
Yu. L. Pavlov, “Ob ob'emakh derevev lesa Galtona – Vatsona s beskonechnoi dispersiei v kriticheskom sluchae”, Diskret. matem., 36:2 (2024), 33–49
M. M. Leri, Yu. L. Pavlov, “Lokalnaya drevovidnost v konfiguratsionnykh grafakh so stepennym raspredeleniem”, Inform. i ee primen., 18:1 (2024), 46–53
Yu. L. Pavlov, “On the limit distribution of the number of vertices in the levels of a Galton–Watson tree”, Math. Notes, 116:3 (2024), 514–520
E. V. Khvorostyanskaya, “On the number of trees of a given size in a Galton–Watson forest in the critical case”, Theory Probab. Appl., 68:1 (2023), 62–76
X. Fu, Y. Chen, J. Yan, Yu. Chen, F. Xu, “BGRF: A broad granular random forest algorithm”, Journal of Intelligent & Fuzzy Systems, 44:5 (2023), 8103
Yu. L. Pavlov, I. A. Cheplyukova, “Sizes of Trees in a Random Forest and Configuration Graphs”, Proc. Steklov Inst. Math., 316 (2022), 280–297
E. V. Khvorostyanskaya, “Limit theorems for the maximal tree size of a Galton – Watson forest in the critical case”, Discrete Math. Appl., 33:4 (2023), 205–217
Yu. L. Pavlov, “On the maximal size of tree in a random forest”, Discrete Math. Appl., 34:4 (2024), 221–232
Citation in format AMSBIB
Contact us: