Phase transitions for random geometric preferential attachment graphs

Jordan, Jonathan; Wade, Andrew R.

doi:10.1239/aap/1435236988

Phase transitions for random geometric preferential attachment graphs

Jordan, Jonathan; Wade, Andrew R.

Authors

Jonathan Jordan

Professor Andrew Wade andrew.wade@durham.ac.uk
Professor

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.