Premium
Random trees and general branching processes
Author(s) -
Rudas Anna,
Tóth Bálint,
Valkó Benedek
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20137
Subject(s) - mathematics , vertex (graph theory) , branching process , branching (polymer chemistry) , combinatorics , random tree , tree (set theory) , preferential attachment , discrete mathematics , degree (music) , limiting , computer science , physics , graph , mechanical engineering , materials science , motion planning , robot , engineering , composite material , complex network , artificial intelligence , acoustics
We consider a tree that grows randomly in time. Each time a new vertex appears, it chooses exactly one of the existing vertices and attaches to it. The probability that the new vertex chooses vertex x is proportional to w (deg( x )), a weight function of the actual degree of x . The weight function w : ℕ → ℝ + is the parameter of the model. In 4 and 11 the authors derive the asymptotic degree distribution for a model that is equivalent to the special case, when the weight function is linear. The proof therein strongly relies on the linear choice of w . Using well‐established results from the theory of general branching processes we give the asymptotical degree distribution for a wide range of weight functions. Moreover, we provide the asymptotic distribution of the tree itself as seen from a randomly selected vertex. The latter approach gives greater insight to the limiting structure of the tree. Our proof is robust and we believe that the method may be used to answer several other questions related to the model. It relies on the fact that considering the evolution of the random tree in continuous time, the process may be viewed as a general branching process, this way classical results can be applied. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007