Phase transitions for random geometric preferential attachment graphs

Jonathan Jordan and Andrew R. Wade

Advances in Applied Probability, 47, no. 2, June 2015, 565–588.

Abstract

We study an evolving spatial network in which sequentially arriving vertices are joined to existing vertices at random according to a rule that combines preference according to degree with preference according to spatial proximity. We investigate phase transitions in graph structure as the relative weighting of these two components of the attachment rule is varied.

Previous work of one of the authors showed that when the geometric component is weak, the limiting degree sequence of the resulting graph coincides with that of the standard Barabási–Albert preferential attachment model. We show that at the other extreme, in the case of a sufficiently strong geometric component, the limiting degree sequence coincides with that of a purely geometric model, the on-line nearest-neighbour graph, which is of interest in its own right and for which we prove some extensions of known results. We also show the presence of an intermediate regime, in which the behaviour differs significantly from both the on-line nearest-neighbour graph and the Barabási–Albert model; in this regime, we obtain a stretched exponential upper bound on the degree sequence.

Our results lend some mathematical support to simulation studies of Manna and Sen, while proving that the power law to stretched exponential phase transition occurs at a different point from the one conjectured by those authors.