























It is well known that many random graphs with infinite variance degrees are ultrasmall. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least $k$ is approximately $k^{-(τ-1)}$ with $τ\in(2,3)$, typical distances between pairs of vertices in a graph of size $n$ are asymptotic to $\frac{2\log\log n}{|\log(τ-2)|}$ and $\frac{4\log\log n}{|\log(τ-2)|}$, respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order $\log\log n$ precisely when the minimal forward degree $d$ of vertices is at least $2$. We identify the exact constant, which equals that of the typical distances plus $2/\log d$. Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。