Prperties of Preferential Attachment Trees with Fitness

Abstract

Preferential Attachment Graphs are a class of random graphs used to model scale-free growing networks. We study Preferential Attachment Trees with constant additive and multiplicative fitness. Degree profile of a specific vertex has been explored by using the well-known technique of writing recursions and some classic results on Triangular Pòlya Urns. In this thesis, we investigate some sub-structures of the Preferential Attachment Trees with constant fitness. In particular, we study the number of cherries and leaves in the tree. We obtain expressions for the expectation of the number of these sub-structures attached to a specific vertex as well as the total number in the tree at time t. Further, by appealing to Pòlya Urns with weights, we also show that the number of these sub-structures scaled with time converges almost surely to a deterministic limit.