Giant descendant trees and matching sets in the preferential attachment graph.
2019
We study the $\delta$-version of the preferential attachment graph with $m$ attachments for each of incoming vertices. We show that almost surely the scaled size of a breadth-first (descendant) tree rooted at a fixed vertex converges, for $m=1$, to a limit whose distribution is a mixture of two beta distributions, and that for $m>1$ the limit is $1$. We also analyze the likely performance of a greedy matching algorithm for all $m\ge 1$ and establish an almost sure lower bound for the size of the matching set.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
31
References
1
Citations
NaN
KQI