The number of descendants in a preferential attachment graph
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929637850873856 |
|---|---|
| author | Janson, Svante Lo, Tiffany Y. Y. |
| author_facet | Janson, Svante Lo, Tiffany Y. Y. |
| contents | We study the number $X^{(n)}$ of vertices that can be reached from the last added vertex $n$ via a directed path (the descendants) in the standard preferential attachment graph. In this model, vertices are sequentially added, each born with outdegree $m\ge 2$; the endpoint of each outgoing edge is chosen among previously added vertices with probability proportional to the current degree of the vertex plus some number $ρ$.
We show that $X^{(n)}/n^ν$ converges in distribution as $n\to\infty$, where $ν$ depends on both $m$ and $ρ$, and the limiting distribution is given by a product of a constant factor and the $(1-ν)$-th power of a Gamma(m/(m-1),1) variable. The proof uses a Pólya urn representation of preferential attachment graphs, and the arguments of Janson (2024) where the same problem was studied in uniform attachment graphs. Further results, including convergence of all moments and analogues for the version with possible self-loops are provided. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_13975 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The number of descendants in a preferential attachment graph Janson, Svante Lo, Tiffany Y. Y. Probability Combinatorics We study the number $X^{(n)}$ of vertices that can be reached from the last added vertex $n$ via a directed path (the descendants) in the standard preferential attachment graph. In this model, vertices are sequentially added, each born with outdegree $m\ge 2$; the endpoint of each outgoing edge is chosen among previously added vertices with probability proportional to the current degree of the vertex plus some number $ρ$. We show that $X^{(n)}/n^ν$ converges in distribution as $n\to\infty$, where $ν$ depends on both $m$ and $ρ$, and the limiting distribution is given by a product of a constant factor and the $(1-ν)$-th power of a Gamma(m/(m-1),1) variable. The proof uses a Pólya urn representation of preferential attachment graphs, and the arguments of Janson (2024) where the same problem was studied in uniform attachment graphs. Further results, including convergence of all moments and analogues for the version with possible self-loops are provided. |
| title | The number of descendants in a preferential attachment graph |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2412.13975 |