Growth of preferential attachment random graphs via continuous-time branching processes (Q949467): Difference between revisions

A graph process \({G(n): n=0,1,\dots}\) starts with a graph \(G(0)\) consisting of a single edge between two vertices. The graph \(G(n+1)\) is obtained from \(G(n)\) by selecting one of the vertices in \(G(n)\) with a probability that is proportional to a linear function of its degree and joining that vertex to a new vertex by \(x(n+1)\) parallell edges. The variables \(x(1), x(2),\dots \) are independent random variables with a common probability distribution on the positive integers. The graph \(G(n)\) can also be described as a tree with random edge weights. Asymptotic results are given for the degrees, the maximum degree, and the degree distribution of \(G(n)\). In particular, the limiting degree distribution exhibits a power-law behavior.