The maximum tree of a random forest in the configuration graph. (September 2021)

• Record Type: Journal Article
• Authors: Pavlov, Yu. L.
• Is Part Of: Sbornik. Volume 212:Number 9(2021)
• Page Start: 1329
• Page End: 1346
• Publication Date: 2021-09
• Subjects: 60C05; random forest -- configuration graph -- tree size -- limit theorems; Mathematics -- Periodicals; 510.5
• DOI: 10.1070/SM9481
• Languages: English
• ISSNs: 1064-5616

Abstract

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.