Loading…

Insertion depth in power-weight trees

•Many real-world networks display attachment preference based on node age.•We introduce a random tree model with preferential attachment based on node index (age).•The form of index (age) preference is controlled by a real-valued parameter.•We study insertion depth in our attachment model and find t...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2022-06, Vol.176, p.106227, Article 106227
Main Authors: Lyon, Merritt, Mahmoud, Hosam
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•Many real-world networks display attachment preference based on node age.•We introduce a random tree model with preferential attachment based on node index (age).•The form of index (age) preference is controlled by a real-valued parameter.•We study insertion depth in our attachment model and find that the behavior varies depending on the value of the parameter. We study the insertion depth in a class of nonuniform random recursive trees grown with an attachment preference for a power of the node index. The strength of index preference is controlled by a real-valued power parameter α; the model accommodates both young-age and old-age preference as specific cases. We find the exact probability law in terms of the Poisson-Binomial distribution, and consequently, the exact and asymptotic mean and variance. Under appropriate normalization, we derive concentration laws and limiting distributions. For α>−1, with logarithmic normalization of the depth, we have a normal limit. The case α=−1 is a critical point at which we retain a normal limit but under an iterated logarithm normalization. For these normal cases, Chen-Stein approximation gives a slow rate of convergence in the Wasserstein distance. The case α
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2021.106227