Universal techniques to analyze preferential attachment trees: Global and Local analysis

Опубликовано 6 сентября 2016, 16:40

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 {\bf 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 and analyzed rigorously by Chayes et al and the Competition Induced Preferential attachment of Berger et al 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 and van der Hofstad et al. In the process we find surprising connections between the degree distributions, Yule processes and $\alpha$-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.