A Multi-type Preferential Attachment Tree

Abstract

A multi-type preferential attachment tree is introduced, and studied using general multi-type branching processes. For the $p$-type case we derive a framework for studying the tree where a type $i$ vertex generates new type $j$ vertices with rate $w_{ij}(n_1,n_2,\dots ,n_p)$ where $n_k$ is the number of type $k$ vertices previously generated by the type $i$ vertex, and $w_{ij}$ is a non-negative function from ${\mathbb{N}}^p$ to $\mathbb{R}$. The framework is then used to derive results for trees with more specific attachment rates. In the case with linear preferential attachment---where type $i$ vertices generate new type $j$ vertices with rate $w_{ij}(n_1,n_2,\dots ,n_p)={\gamma }_{ij}(n_1+n_2+\cdots +n_p)+{\beta }_{ij}$, where ${\gamma }_{ij}$ and ${\beta }_{ij}$ are positive constants---we show that under mild regularity conditions on the parameters $\{{\gamma }_{ij}\},\{{\beta }_{ij}\}$ the asymptotic degree distribution of a vertex is a power law distribution. The asymptotic composition of the vertex population is also studied.