Asymptotic diameter of preferential attachment model
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913008468361216 |
|---|---|
| author | Du, Hang Gong, Shuyang Li, Zhangsong Zhu, Haodong |
| author_facet | Du, Hang Gong, Shuyang Li, Zhangsong Zhu, Haodong |
| contents | We study the asymptotic diameter of the preferential attachment model $\operatorname{PA}\!_n^{(m,δ)}$ with parameters $m \ge 2$ and $δ> 0$. Building on the recent work \cite{VZ25}, we prove that the diameter of $G_n \sim \operatorname{PA}\!_n^{(m,δ)}$ is $(1+o(1))\log_νn$ with high probability, where $ν$ is the exponential growth rate of the local weak limit of $G_n$. Our result confirms the conjecture in \cite{VZ25} and closes the remaining gap in understanding the asymptotic diameter of preferential attachment graphs with general parameters $m \ge 1$ and $δ>-m$. Our proof follows a general recipe that relates the diameter of a random graph to its typical distance, which we expect to have applicability in a broader range of models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_21741 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotic diameter of preferential attachment model Du, Hang Gong, Shuyang Li, Zhangsong Zhu, Haodong Probability Combinatorics 05C80, 05C82 We study the asymptotic diameter of the preferential attachment model $\operatorname{PA}\!_n^{(m,δ)}$ with parameters $m \ge 2$ and $δ> 0$. Building on the recent work \cite{VZ25}, we prove that the diameter of $G_n \sim \operatorname{PA}\!_n^{(m,δ)}$ is $(1+o(1))\log_νn$ with high probability, where $ν$ is the exponential growth rate of the local weak limit of $G_n$. Our result confirms the conjecture in \cite{VZ25} and closes the remaining gap in understanding the asymptotic diameter of preferential attachment graphs with general parameters $m \ge 1$ and $δ>-m$. Our proof follows a general recipe that relates the diameter of a random graph to its typical distance, which we expect to have applicability in a broader range of models. |
| title | Asymptotic diameter of preferential attachment model |
| topic | Probability Combinatorics 05C80, 05C82 |
| url | https://arxiv.org/abs/2504.21741 |