(Under reasonable assumptions, each of
us is connected to everyone else by an average of three links, although
we’re not likely to know who the two intermediate parties are.)
Another variant of the notion concerns the
number of movie links between film actors, say between Marlon Brando and
Christina Ricci, or between Kevin Bacon and anyone else. If A and B
appeared together in X, and B and C appeared together in Y, then A is
linked to C via these two steps.
Web
Links
Ideas about such informal networks are good for more
than parlor games. They’re proving useful in analyzing the structure,
shape and “diameter” of the World Wide Web, which now contains something
like 800 million documents.
How are these 800
million Web pages connected? How many links does the average Web page
contain? What constitutes a good search strategy?
And perhaps most importantly, how many clicks
on average does it take to get from one of two randomly selected documents
to another?
The answer: An average 19 clicks
can take you from this page to most any other page on the Web.
Recently, Albert-Laszlo Barabasi, a physics
professor at Notre Dame, and two associates, Reka Albert and Hawoong
Jeong, published results that strongly suggest that the Web is growing and
that its documents are linking in a rather collective way that accounts
for, among other things, the unexpectedly large number of very popular
documents.
Flocking on the
Web
The increasing number of Web pages and the “flocking
effect” of many pages pointing to the same popular addresses, causing
proportionally more pages to do the same thing, leads to a so-called
power law.
Specifically, Barabasi,
Albert and Jeong show that the probability that a document has k links is
roughly proportional to 1/k3 — or inversely proportional to the
third power of k. (I’ve rounded off; the model predicts 2.9.)
This means, for example, that there are
approximately one-eighth as many documents with 20 links as there are
documents with 10 links since 1/203 is one-eighth of
1/103. Thus, the number of documents with k links declines
quickly with k, but nowhere near as quickly as a normal bell-shaped
distribution would have predicted.
[The power
laws that characterize the Web also seem to characterize many other
complex systems that self-organize into a state of skittish
responsiveness.
Per Bak, a physicist at the
Niels Bohr Institute in Denmark, has claimed that such 1/km
laws (for various values of m) are typical of many biological, geological,
linguistic, musical and economic processes, and that they arise whenever
we examine complex systems of any sort.]
World
Not-So-Wide Web
The most intriguing consequence of the
Barabasi, Albert, Jeong model, however, is that because of the power law
distribution of links to and from documents on Web sites, the diameter of
the Web is only 19 clicks wide, far fewer than had been conjectured.
On the other hand, comparing 19 with the much
smaller number of links between arbitrarily selected people, we may wonder
why the diameter is as big as it is.
The
answer is that the average Web page contains only seven links, whereas the
average person knows hundreds of people.
Even
though the Web is expected to grow by a power of 10 the next few years,
its diameter is likely to grow by only a couple of clicks, from 19 to 21.
The growth and preferential linking assumptions above indicate that the
Web’s diameter D is governed by a logarithmic law; D is a bit more than 2
log(N), where N is the number of documents, presently 800 million.
Not Too
Daunting
If the Barabasi et al. model is valid (and more
work needs to be done), we can be assured that the Web is not quite as
unmanageable and untraversable as it often seems.
The model also underscores the deficiencies
of many traditional search engines that locate information by indexing and
matching strings of words; such an approach requires a burdensome and
time-consuming search of a vast number of sites, most of which are
irrelevant.
Better, it turns out, are search
engines like Yahoo!, which uses humans to select and catalogue sites, or
newcomers like Google, which takes advantage of the link structure of the
Web itself and gives more weight to important sites.
The World Wide Web is taking the shape of the
messy network of people who are creating it. 
Professor of
mathematics at Temple University, John
Allen Paulos is the author of several books, including A
Mathematician Reads the Newspaper and, most recently, Once Upon a
Number. His Who’s Counting? column on ABCNEWS.com appears on the
first day of every month.
HOME
.gif){kind=small}
.gif){kind=small}
SPECIAL SERVICES
