Universal techniques to analyze preferential attachment trees : Global and Local analysis
Universal techniques to analyze preferential attachment trees : Global and Local analysis
复制标题
分析优先附着树的通用技术：全局和局部分析
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
S. Bhamidi
中科院分区：
文献类型：
--
作者：
S. Bhamidi
我们使用连续时间分支过程中的嵌入来推导与不同偏好依恋模型相关的各种统计的渐近性。这种强大的方法使我们能够在一个共同的框架下，用很少的努力，不仅推断出大量无尺度树的局部特征，而且还推断出全局特征，如树的高度、最大度、附着在根上的渗透成分的大小和结构。我们展示了我们对一些不同的优先依恋图模型的计算。在此过程中，我们得到了大量优先依恋模型的精确结果，其中不仅包括通常的优先依恋，还包括Barabasi等人（[6]）引入的具有适应度的优先依恋，以及Berger等人（[5]）的竞争诱导优先依恋。虽然目前流行的大多数技术都可以获得树的渐近度分布，但我们展示了嵌入技术如何揭示这些树的局部和全局特征的更多信息。同样，非常温和的论点给了我们一些优先依恋网络模型（不仅仅是树）的渐近度分布和最大度的大小，这些模型是由Cooper和Frieze b[11]和van der Hofstad等人b[12]提出的。在此过程中，我们发现了度分布、Yule过程和α-稳定从属关系之间的惊人联系。我们最后对这些模型的各种统计的渐近性进行了一些猜想，包括这些树上渗透的最大分量的大小。
We use embeddings in continuous time Branching processes to derive asymptotics for various statistics associated with different models of preferential attachment. This powerful method allows us to deduce, with very little effort, under a common framework, not only local characteristics for a wide class of scale free trees, but also global characteristics such as the height of the tree, maximal degree, and the size and structure of the percolation component attached to the root. We exhibit our computations for a number of different graph models of preferential attachment. En-route we get exact results for a large number of preferential attachment models including not only the usual preferential attachment but also the preferential attachment with fitness as introduced by Barabasi et al ([6]) and the Competition Induced Preferential attachment of Berger et al ([5]) to name just two. While most of the techniques currently in vogue gain access to the asymptotic degree distribution of the tree, we show how the embedding techniques reveal significantly more information both on local and global characteristics of these trees. Again very soft arguments give us the asymptotic degree distribution and size of the maximal degree in some Preferential attachment network models (not just trees) formulated by Cooper and Frieze [11] and van der Hofstad et al [12]. In the process we find surprising connections between the degree distributions, Yule processes and α-stable subordinators. We end with a number of conjectures for the asymptotics for various statistics of these models including size of the maximal component in percolation on these trees.