Asymptotic behavior and distributional limits of preferential attachment graphs (Q2438744): Difference between revisions

This paper investigates the weak limit of the a random graph that is constructed via the Barabási-Albert model. The authors consider a variation of the Barabási-Albert model which does not create loops. They consider three versions of it which they call the independent model, the conditional model and the sequential model, respectively. In each one of the models, each incoming vertex throws \(m\) edges to the existing graph and the way these are attached to the existing vertices defines the above models. In the independent model, each one of the \(m\) neighbours is chosen independently with probability proportional to the degree of the chosen vertex. The conditional model is a variation of the independent model where, when the \(m\) neighbours are chosen, no multiple edges are created. Finally, the sequential model is a interpolation between the preferential attachment and the uniform choice of neighbours: each one of the \(m\) edges chooses a neighbour either uniformly, with probability \(\alpha\), among the existing vertices or, with probability \(1-\alpha\), a vertex is chosen with probability proportional to its degree. The first result of the paper gives a ``static'' version of the distribution of the resulting random graph which they call the Pólya urn representation. Subsequently, they show that this sequence converges to a certain limiting random graph which the authors call the Pólya-point graph. The convergence here is in the Benjamini-Schramm sense, which is related to the isomorpshism type of the neighbourhood of a randomly chosen vertex. The authors also use a lemma that is due to Lovasz to deduce also the convergence of small subgraph frequencies, which they determine.