Vol. 286 15 October 1999, pp. 509-512
Lada A. Adamic, Bernardo A. Huberman
PDF version
A recent paper by Barabasi and Albert 'Emergence of Scaling in Random
Networks', Vol. 286 15 October 1999, pp. 509-512 , proposes an improved
version of the Erdos Renyi theory of random networks in order to account for the
scaling properties of a number of systems, including the link structure of the
World Wide Web. We wish to point out that the theory they present is
inconsistent with empirically observed properties of the web link structure.
Barabasi and Albert write: "Because of the preferential attachment, a vertex
that acquires more connections than another one will increase its connectivity
at a higher rate; thus, an initial difference in the connectivity between two
vertices will increase further as the network grows... Thus older [] vertices
increase their connectivity at the expense of the younger []ones, leading over
time to some vertices that are highly connected, a "rich-get-richer"
phenomenon." This is demonstrated clearly in Fig 2c) in the original paper.
It is this prediction of the Barabasi-Albert (BA) model that renders it
unable to account for the power law distribution of links in the WWW (Fig. 1b in
the original paper). We studied a crawl of 260,000 sites, where each site is a
separate domain name. We counted how many links the sites received from other
sites. As for pages, the distribution of links among sites, shown in Fig. 1, is
power law. Next we queried the Internic database (1) for the date the site was
originally registered. Whereas the BA model predicts that older sites not only
have an advantage for having more time to acquire links, but gather links at a
faster rate than newer sites, our data, shown in Fig. 2, demonstrates that, in
fact, there is no correlation between the age of a site and the number of links
it has.
The absence of correlation between age and the number of links is hardly
surprising. All sites are not created equal. A site with very popular content,
which appears in 1999, will soon have more links than a bland site created in
1993. It is likely that the rate of acquisition of new links is proportional to
the number of links the site has already. After all, the more links a site has,
the more visible it becomes, the more new links it will get. However, there
should be an additional proportionality factor, or growth rate, which varies
from site to site.
Our recently proposed theory (2), which accounts for the power law
distribution in the number of pages per site, can also be applied to the number
of links a site receives. In this model, at each time step the number of new
links a site receives is a random fraction of the number of links the site
already has. New sites appear at an exponential rate and each has a different
growth rate. This model yields scatter plots similar to the one shown in Fig. 2
and can produce any exponent g > 1.
References:
1. http://www.networksolutions.com/
2. B.A. Huberman and L.A. Adamic, Nature 401, 131 (1999).
|
printable version
