A Random Graph Model for Power Law Graphs

Abstract

We propose a random graph model which is a special case of sparserandom graphs with given degree sequences which satisfy a power law. This model involves only a small number of paramo eters, called logsize and log-log growth rate. These parameters capture some universal characteristics of massive graphs. From these parameters, various properties of the graph can be derived. For example, for certai n ranges of the parameters, we wi II compute the expected distribution of the sizes of the connected components which almost surely occur with high probability. We illustrate the consistency of our model with the behavior of some massive graphs derived from data in telecommunications. We also discuss the threshold function, the giant component, and the evolution of random graphs in this model.