Vertices of high degree in the preferential attachment tree
Vertices of high degree in the preferential attachment tree
复制标题
优先附着树中高度高的顶点
DOI：
10.1214/ejp.v17-1803
复制
发表时间：
2010
影响因子：
1.4
通讯作者：
M. Luczak
中科院分区：
文献类型：
--
作者：
G. Brightwell;M. Luczak
我们研究基本的优先附着过程，该过程生成一系列随机树，每棵随机树都是通过引入一个新顶点并将其连接到一个现有顶点而从前一棵树获得的，选择的概率与其度数成正比。 我们研究每次 $t$ 时每个度 $\ell$ 的顶点数量 $D_t(\ell)$，特别关注 $\ell$ 是 $t$ 的增长函数的情况。我们表明，对于所有 $\ell \le (t/\log t)^{-1/3}$，$D_t(\ell)$ 集中在其均值附近，即大约 $4t/\ell^3$；这最好达到对数因子。
We study the basic preferential attachment process, which generates a sequence of random trees, each obtained from the previous one by introducing a new vertex and joining it to one existing vertex, chosen with probability proportional to its degree. We investigate the number $D_t(\ell)$ of vertices of each degree $\ell$ at each time $t$, focussing particularly on the case where $\ell$ is a growing function of $t$. We show that $D_t(\ell)$ is concentrated around its mean, which is approximately $4t/\ell^3$, for all $\ell \le (t/\log t)^{-1/3}$; this is best possible up to a logarithmic factor.