 |
1.5 billion Web pages linked by 19 clicks of separation
Internet expansion is similar to plant growth, scientists find
Monday, February 7, 2000
By TOM PAULSON
The World Wide Web is growing like a weed. Literally.
Scientists say it's developing according to the same organizing patterns and mathematical principles observed among plant life in the wild.
Nobody knows exactly why.
The rapidly expanding Web today has about 1.5 billion pages. But some scientists think its size is best measured by the average number of connections it takes to link any two random sites.
Thus was born the "19 clicks of separation" theory of the Web. This scientific effort to size the Web has helped reveal the organic way in which the global network is growing.
Like the celebrated "six degrees of separation" that supposedly can connect any two people on the planet, researchers at the University of Notre Dame recently estimated that any two randomly selected sites on the Web are connected, on average, by 19 clicks.
The original six-degrees notion, based on a sociological theory popularized in the 1960s, posits that each person on the planet is linked to any other person through no more than five mutual acquaintances. Out of the total 6 billion people on Earth, you can get from one person to anyone else in at most six people.
The Notre Dame team says, on average, you can get from one site on the Web to any other randomly selected site in about 19 clicks.
"Based on this kind of information, we can construct more effective search engines," said Hawoong Jeong, one of the Notre Dame scientists.
Today's search engines typically cover less than one-fifth of all publicly indexed sites on the Web.
The 19-clicks theory, while interesting, has left other Web experts less than impressed.
"Who cares?" responded Oren Etzioni, developer of the search engine Metacrawler and a University of Washington computer scientist on leave while working as chief technology officer at the Web company Go2net.com.
"Whether the Web's diameter is 11 or 19 or 7.5 might be a fun academic curiosity, but that's not how people use the Web," Etzioni said.
What's more interesting to Etzioni is the Web's structure.
When the Notre Dame researchers tried to find a meaningful way to describe the diameter of the Web, they also demonstrated something mysterious about its growth and development.
Basically, they found that the Web is a lot like a living plant. For some unknown reason, it is developing along the same mathematical principles that govern the organic development of plants in the natural world.
"It was a complete surprise for us," said Albert-Laszlo Barabasi, a physicist at Notre Dame and principal investigator for the team that reported their finding on the Web's 19 clicks of separation. It was reported last fall in the journal Nature.
Barabasi and his students, Jeong and Reka Albert, last year set loose a "robot" search engine on portions of the Web to tally links and measure how far away each of the links encountered were from one another. The robotic search engine was a computer program that traveled the Web documenting its encounters.
Barabasi said everyone expected the robot to encounter a simple, exponentially increasing number of links based on the assumption that the links on the Web are distributed randomly.
Instead, he said, the data clearly showed the links are distributed according to a more sophisticated and self-organizing mathematical principle known as the "power-tail law." Nobody knows why.
Another team of researchers, Bernardo Huberman and Lada Adamic at Xerox Palo Alto Research Center, found the same growth pattern on the Web through a different method of analysis. Their findings were also reported in Nature.
"It's just like the growth of a tree," Huberman said. "The more pages a site has, the more likely it is that more pages will be added to it."
Just as the number of branches on a tree limb is greater near the trunk than out at the tip, growth on the Web takes place so that links with more associated links (or branches) end up closer to the Web's "trunk."
This cybertrunk is perhaps best thought of as the main flow of information on the Web.
Because the Web does not exist in physical space and its "branches" always reconnect rather than spread out into thin air, the tree analogy is not perfect.
But the point is that the Web's growth appears to follow some of the same natural laws at work in ecological systems.
"What's most interesting is how the Web's structure has evolved without any central authority," said Steve Lawrence, a computer scientist at Princeton University and at NEC. He has been internationally recognized for his work on Web information distribution and access.
"It's ending up with a high degree of structure," Lawrence said, and it's somehow creating that structure on its own.
Barabasi and his students demonstrated that efforts aimed at quantifying the Web can aid in the effort to better understand its structure. The Notre Dame researchers play around in the field of "topology" -- a branch of mathematics in which number and shape are the same thing.
As the number of Web pages increases over time, Barabasi said, the Web's size -- degree of separation -- can be expected to increase slowly.
It will not increase as fast as might be expected based on simple exponential growth, he said.
If it operates according to the power-tail law, Barabasi said, a tenfold increase in the number of pages on the Web probably would result in just a small increase in Web size (again, size being the degree of separation between links).
But again, Etzioni said, so what if it does? The real trick here is to make more efficient and accurate search engines, he said.
"The typical search engine today only indexes about 16 percent of the Web," Etzioni said. "That fraction keeps getting smaller as the Web increases in size."
The key to getting better search engines, many of these Web experts say, is to better understand how the Web is organized -- why it's growing like a weed -- and how to use that knowledge to improve our ability to find the information we seek.
P-I reporter Tom Paulson can be reached at 206-448-8318 or tompaulson@seattle-pi.com
SEATTLE POST-INTELLIGENCER REPORTER
· Burglar beaten by would-be victims
· Zoo gazelle dies from injuries
· River trail to be closed for construction around UW Bothell campus
· McDermott balks at rule requiring removal of war memorials
· Divers to clean up Green Lake's junk
· 520 tolls may stretch from I-5 to Bellevue
· Fifth dental death in 3 years
· Plane hopper has worn out cute welcome
· Stepson faces jury in for-hire slaying
· Agencies asked to ease safety rules
· Officer's firing unjustified, board says
· State race for public lands chief could get rough
more
101 Elliott Ave. W.
Seattle, WA 98119
(206) 448-8000
Home Delivery: (206) 464-2121 or (800) 542-0820
seattlepi.com serves about 1.7 million unique visitors
and 30 million page views each month.
Send comments to newmedia@seattlepi.com
Send investigative tips to iteam@seattlepi.com
©1996-2008 Seattle Post-Intelligencer
Terms of Use/Privacy Policy
