Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-02-06T22:17:04.577Z Has data issue: false hasContentIssue false
  • English
  • Français

Robust Analysis of Preferential Attachment Models with Fitness

Published online by Cambridge University Press:  24 February 2014

STEFFEN DEREICH  and
MARCEL ORTGIESE
STEFFEN DEREICH
Affiliation:
Institut für Mathematische Statistik, Westf. Wilhelms-Universität Münster, Einsteinstraße 62, 48149 Münster, Germany (e-mail: Steffen.Dereich@wwu.de)
MARCEL ORTGIESE
Affiliation:
Institut für Mathematische Statistik, Westf. Wilhelms-Universität Münster, Einsteinstraße 62, 48149 Münster, Germany (e-mail: Steffen.Dereich@wwu.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The preferential attachment network with fitness is a dynamic random graph model. New vertices are introduced consecutively and a new vertex is attached to an old vertex with probability proportional to the degree of the old one multiplied by a random fitness. We concentrate on the typical behaviour of the graph by calculating the fitness distribution of a vertex chosen proportional to its degree. For a particular variant of the model, this analysis was first carried out by Borgs, Chayes, Daskalakis and Roch. However, we present a new method, which is robust in the sense that it does not depend on the exact specification of the attachment law. In particular, we show that a peculiar phenomenon, referred to as Bose–Einstein condensation, can be observed in a wide variety of models. Finally, we also compute the joint degree and fitness distribution of a uniformly chosen vertex.

Keywords

Primary 05C80Secondary 60G4290B15
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 3 , May 2014 , pp. 386 - 411
Copyright
Copyright © Cambridge University Press 2014 

References

[1]Barabási, A.-L. and Albert, R. (1999) Emergence of scaling in random networks. Science 286 (5439)509–512.Google Scholar
[2]Benaïm, M. (1999) Dynamics of stochastic approximation algorithms. In Séminaire de Probabilités XXXIII, Vol. 1709 of Lecture Notes in Mathematics, Springer, pp. 1–68.Google Scholar
[3]Bhamidi, S. (2007) Universal techniques to analyze preferential attachment trees: Global and local analysis. Preprint available at http://www.unc.edu/~bhamidi/.Google Scholar
[4]Bianconi, G. and Barabási, A.-L. (2001) Bose–Einstein condensation in complex networks. Phys. Rev. Lett. 86 5632–5635.Google Scholar
[5]Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G. (2001) The degree sequence of a scale-free random graph process. Random Struct. Alg. 18 279–290.Google Scholar
[6]Borgs, C., Chayes, J., Daskalakis, C. and Roch, S. (2007) First to market is not everything: An analysis of preferential attachment with fitness. In STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, pp. 135–144.Google Scholar
[7]Cooper, C. and Frieze, A. (2003) A general model of web graphs. Random Struct. Alg. 22 311–335.CrossRefGoogle Scholar
[8]Deijfen, M., van den Esker, H., van der Hofstad, R. and Hooghiemstra, G. (2009) A preferential attachment model with random initial degrees. Ark. Mat. 47 41–72.Google Scholar
[9]Dereich, S. (2013) Random networks with preferential attachment: Unfolding Bose–Ein-stein conden-sation. In preparation.Google Scholar
[10]Dereich, S. and Mörters, P. (2009) Random networks with sublinear preferential attachment: Degree evolutions. Electron. J. Probab. 14 1222–1267.Google Scholar
[11]Dereich, S. and Mörters, P. (2013) Emergence of Condensation in Kingman's Model of Selection and Mutation. Acta Appl. Math. 127 (1)17–26.CrossRefGoogle Scholar
[12]Hagberg, O. and Wiuf, C. (2006) Convergence properties of the degree distribution of some growing network models. Bull. Math. Biol. 68 1275–1291.Google Scholar
[13]van der Hofstad, R. (2013) Random Graphs and Complex Networks. Lecture notes in preparation, available at http://www.win.tue.nl/~rhofstad/.Google Scholar
[14]Jordan, J. (2006) The degree sequences and spectra of scale-free random graphs. Random Struct. Alg. 29 226–242.Google Scholar
[15]Jordan, J. (2010) Degree sequences of geometric preferential attachment graphs. Adv. Appl. Probab. 42 319–330.Google Scholar
[16]Jordan, J. (2013) Geometric preferential attachment in non-uniform metric spaces. Electron. J. Probab. 18 #15.Google Scholar
[17]Nerman, O. (1981) On the convergence of supercritical general (C-M-J) branching processes. Z. Wahrsch. Verw. Gebiete 57 365–395.CrossRefGoogle Scholar
[18]Newman, M. (2010) Networks: An Introduction, Oxford University Press.Google Scholar
[19]Pemantle, R. (2007) A survey of random processes with reinforcement. Probab. Surv. 4 1–79.Google Scholar
[20]Robbins, H. and Monro, S. (1951) A stochastic approximation method. Ann. Math. Statist. 22 400–407.Google Scholar
[21]Rudas, A., Tóth, B. and Valkó, B. (2007) Random trees and general branching processes. Random Struct. Alg. 31 186–202.CrossRefGoogle Scholar