Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-14T09:29:27.077Z 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: [email protected])
MARCEL ORTGIESE
Affiliation:
Institut für Mathematische Statistik, Westf. Wilhelms-Universität Münster, Einsteinstraße 62, 48149 Münster, Germany (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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