Geometric preferential attachment in non-uniform metric spaces

Jonathan H Jordan (University of Sheffield)


We investigate the degree sequences of geometric preferential attachment graphs in general compact metric spaces. We show that, under certain conditions on the attractiveness function, the behaviour of the degree sequence is similar to that of the preferential attachment with multiplicative fitness models investigated by Borgs et al. When the metric space is finite, the degree distribution at each point of the space converges to a degree distribution which is an asymptotic power law whose index depends on the chosen point. For infinite metric spaces, we can show that for vertices in a Borel subset of S of positive measure the degree distribution converges to a distribution whose tail is close to that of a power law whose index again depends on the set.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-15

Publication Date: January 14, 2013

DOI: 10.1214/EJP.v18-2271


  • R. Albert, A.-L. Barabási, and H. Jeong. Mean-field theory for scale-free random networks. Physica A, 272:173--187, 1999.
  • N. Berger, B. Bollobás, C. Borgs, J. Chayes, , and O. Riordan. Degree distribution of the FKP network model. In Automata, Languages and Programming.
  • Bollobás, Béla; Riordan, Oliver. The diameter of a scale-free random graph. Combinatorica 24 (2004), no. 1, 5--34. MR2057681
  • Bollobás, Béla; Riordan, Oliver; Spencer, Joel; Tusnády, Gábor. The degree sequence of a scale-free random graph process. Random Structures Algorithms 18 (2001), no. 3, 279--290. MR1824277
  • Borgs, Christian; Chayes, Jennifer; Daskalakis, Constantinos; Roch, Sebastien. First to market is not everything: an analysis of preferential attachment with fitness. STOC'07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 135--144, ACM, New York, 2007. MR2402437
  • Flaxman, Abraham D.; Frieze, Alan M.; Vera, Juan. A geometric preferential attachment model of networks. Internet Math. 3 (2006), no. 2, 187--205. MR2321829
  • Flaxman, Abraham D.; Frieze, Alan M.; Vera, Juan. A geometric preferential attachment model of networks. II. Internet Math. 4 (2007), no. 1, 87--111. MR2492176
  • E. Jacob and P. Mörters. Spatial preferential attachment networks: Power laws and clustering coefficients.
  • Jordan, Jonathan. Degree sequences of geometric preferential attachment graphs. Adv. in Appl. Probab. 42 (2010), no. 2, 319--330. MR2675104
  • Pemantle, Robin. A survey of random processes with reinforcement. Probab. Surv. 4 (2007), 1--79. MR2282181
  • Penrose, Mathew. Random geometric graphs. Oxford Studies in Probability, 5. Oxford University Press, Oxford, 2003. xiv+330 pp. ISBN: 0-19-850626-0 MR1986198
  • Wade, Andrew R. Asymptotic theory for the multidimensional random on-line nearest-neighbour graph. Stochastic Process. Appl. 119 (2009), no. 6, 1889--1911. MR2519349

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.