Popularity based random graph models leading to a scale-free degree sequence Original Research Article

As an extremely simplified model for the growth of the world wide web, Dorogovtsev et al. (Phys. Rev. Lett. 85 (2000) 4633) and Drinea et al. (Variations on random graph models for the web, Technical Report, Department of Computer Science, Harvard University, 2001) introduced the following random graph model, which generalizes an earlier model of Barabási and Albert (Science 286 (1999) 509): at each time step we add a new vertex incident to r edges. The other endpoints of these edges are chosen with probability proportional to their in-degrees plus an initial attractiveness ar, where a is a constant. For all a, r∈N, we determine the asymptotic form of the degree distribution for most of the vertices. Confirming non-rigorous arguments of Dorogovtsev et al. and Drinea et al., this shows that for such a, the proportion P(d) of vertices of degree d almost surely obeys a power law, where P(d) is of the form d−2−a for large d. The case a=1 (which corresponds to the model of Barabasi and Albert) was proved earlier by Bollobás et al. (Random Struct. Algorithms 18 (2001) 279).