The study of random graphs dates back to the work of Erdös and Rényi whose seminal papers [8,9] laid the foundation for the theory of random graphs. There are three standard models for what we will call here uniform random graphs [5]. Each has two parameters. One parameters controls the number of nodes in the graph and one controls the density, or number of edges. For example, the random graph model G(n,m) assigns uniform probability to all graphs with n nodes and m edges while in the random graph model G'(n,p) each edge in an n node graph is chosen with probability p. All these classical models predict that the degree sequence distribution follows Poisson distribution. But the massive graphs from real world shows the degree sequence distribution follows Power Law distribution, which allows existing of large degree vertices. However, the techniques and methodologies developed by Erdös, Rényi and many other people are invaluable and are applied to new models.
Kumar et al. [13,14] and Kleinberg et al. [12] have measured the degree sequences of the Web and shown that it is well approximated by a power law distribution. This was reported independently by Albert, Barabási and Jeong in [4],[6],[7]. The power law distribution of the degree sequence appears to be a very robust property of the Web despite its dynamic nature. In fact, the power law distribution of the degree sequence may be a ubiquitous characteristic, applying to many massive real world graphs. Indeed, Abello et al. [1] have shown that the degree sequence of so called call graphs is nicely approximated by a power law distribution. Call graphs are graphs of calls handled by some subset of telephony carriers for a specific time period. In addition, Faloutsos, et al. [10] have shown that the degree sequence of the Internet router graph also follows a power law.
Several other papers have taken a more or less similar approach to modeling power law
graphs [3,6,7,12,14]. The essential idea is to define a random process
for growing a graph by adding nodes and edges. But the difference to our models exists.
For example, [6,7] implicitly assume that the probability that a node has a
given degree is a continuous function. The authors of [12,14] will offer an
improved analysis in an upcoming paper [18]. Second, while the models may
generate graphs with power law degree sequences, it remains to be seen if they generate
graphs which duplicate other structural properties of the Web, the Internet, and call
graphs. For example, the model in [6,7] cannot generate graphs with a power
law other than p=3. Moreover, all the graphs can be decomposed into
m disjoint
trees, where m is a parameter of the model. The
α,β)
model in
[14] is able to generate graphs for which the power law for the indegree is
different than the power law for the outdegree as is the case for the Web. However, to
do so, the model requires that there be nodes that have only indegree and no outdegree
and visa versa. While this may be appropriate for call graphs (e.g., customer service
numbers) it remains to be seen whether it models the Web.
