Phase transitions for random geometric preferential attachment graphs

Jordan, Jonathan; Wade, Andrew R.

Abstract

Vertices arrive sequentially in space and are joined to existing vertices at random according to a preferential rule combining degree and spatial proximity. We investigate phase transitions in the resulting graph as the relative strengths of these two components of the attachment rule are varied. Previous work of one of the authors showed that when the geometric component is weak, the limiting degree sequence mimics 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 mimics a purely geometric model, the on-line nearest-neighbour graph, for which we prove some extensions of known results. We also show the presence of an intermediate regime, with behaviour distinct 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.

Citation

Jordan, J., & Wade, A. R. (2015). Phase transitions for random geometric preferential attachment graphs. Advances in Applied Probability, 47(2), 565-588. https://doi.org/10.1239/aap/1435236988

• Journal Article Type: Article
• Acceptance Date: Jun 5, 2014
• Online Publication Date: Jun 25, 2015
• Publication Date: Jun 25, 2015
• Deposit Date: Jun 5, 2014
• Publicly Available Date: Oct 28, 2014
• Journal: Advances in Applied Probability
• Print ISSN: 0001-8678
• Electronic ISSN: 1475-6064
• Publisher: Applied Probability Trust
• Peer Reviewed: Peer Reviewed
• Volume: 47
• Issue: 2
• Pages: 565-588
• DOI: https://doi.org/10.1239/aap/1435236988
• Keywords: Random spatial network, Preferential attachment, On-line nearest-neighbour graph, Degree sequence.
• Public URL: https://durham-repository.worktribe.com/output/1459385