Community modulated recursive trees and population dependent branching processes. Issue 2 (21st June 2021)

• Record Type: Journal Article
• Authors: Bhamidi, Shankar; Fan, Ruituo; Fraiman, Nicolas; Nobel, Andrew
• Is Part Of: Random structures & algorithms. Volume 60:Issue 2(2022)
• Page Start: 201
• Page End: 232
• Publication Date: 2021-06-21
• Subjects: community detection -- continuous time branching processes -- inhomogeneous random trees -- multitype branching processes -- random recursive trees -- stochastic block model; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21027
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We consider random recursive trees that are grown via community modulated schemes that involve random attachment or degree based attachment. The aim of this article is to derive general techniques based on continuous time embedding to study such models. The associated continuous time embeddings are not branching processes: individual reproductive rates at each time t depend on the composition of the entire population at that time, and hence vertices do not reproduce independently. Using stochastic analytic techniques we show that various key macroscopic statistics of the continuous time embedding stabilize, allowing asymptotics for a host of functionals of the original models to be derived.