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...
Saved in:
Published in: | Information processing letters 2022-06, Vol.176, p.106227, Article 106227 |
---|---|
Main Authors: | , |
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!
|
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 |