Dec. 1 — Everyone has heard exclamations such as, “Oh, you must know my crazy brother-in-law’s ex-therapist’s plumber,” and most have heard of the alleged six degrees of separation between any two people in this country.
(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.
