The Web is booming like the U.S. economy in at least one respect: The rich are getting richer. In two recent studies, researchers have found that the proportion of Web pages with many outside links pointing toward the page is much higher than would be expected in a random network, probably because people adding new pages tend to link to already-popular sites. As a result, the number of steps it takes to move from place to place stays very small, even as the Web grows exponentially in size.
Albert-László Barabási, a physicist at the University of Notre Dame in Indiana, and two colleagues analyzed the links into and out from the 325,729 pages on Notre Dame's domain, "nd.edu." They found that the pages followed a distribution known as a "power law": That is, the number of pages with n links was proportional to 1/n2, so that pages with 20 links were one-quarter as frequent as those with 10 links. This pattern is "typical of self-organizing systems," such as neural networks, Barabási says. His team found that the law accurately described some other domains (such as whitehouse.gov), so the researchers assume it works for the estimated 800 million pages on the entire Web. If so, then several dozen pages have 1000 or more incoming links. If people had simply linked their pages with other Web pages at random, pages with at least 1000 links would be virtually nonexistent, the team reports in today's Nature. Another team at Cornell and IBM presented a nearly identical power law at the WWW8 conference in Toronto earlier this year.
From the power law, Barabási deduced that the average number of clicks it takes to get from any page on the Web to any other is only 18--and will increase to just 20 if the Web grows by a factor of 10. "If you know where you're going, you can really get there quickly," says Lee Giles, a Web metrologist at NEC Corp. in New Jersey.