Scaled links make nets navigable
By Eric Smalley, Technology Research NewsActor Kevin Bacon in a fractal T-shirt makes a pretty good symbol for a mathematical principle that could yield better routing algorithms and search engines. The principle, discovered by Cornell computer scientist Jon Kleinberg, describes the most efficient structure for networks like the World Wide Web.
Kevin Bacon is the poster boy for the concept that anyone can reach anyone else through six or fewer someone-who-knows-someone connections. And the fundamental principle behind fractals is that the geometries of a particular image remain the same however much a viewer zooms in or out. This is because each shape is made up of many smaller versions of the same shape.
Combine the notion of six degrees of separation with the same-at-every-scale property of fractal geometry and you have in a nutshell Kleinberg's algorithm for making a network easier to navigate.
People don't need a bird's eye view of a network to navigate it efficiently. We wanted to understand what about networks makes that possible, Kleinberg said.
Kleinberg found the answer in the structure of network connections. Many networks have short chains, which means they have relatively few links between any two points. But some short chain networks are easier to navigate than others. It's harder to find the short chains in networks where individual nodes have substantially more local links than long distance links or vice versa.
Put in terms of a social network, the most efficient structure for navigating a network is one in which individuals have as many friends in their counties as in their towns minus the friends in the towns, as many friends in their states as in their counties minus the friends in the counties, and as many friends in the country as in their states minus the friends in the states, Kleinberg said.
"These local navigation algorithms seem to work best when the network is equally rich in links at all of these length scales. This is a network with a sort of built-in gradient that funnels you toward targets. No one individual knows the short chains. But if they simply start forwarding [a message] in the right direction then somehow the structure of the network actually works to funnel it in on the target," he said.
In addition to figuring out how this network principle can be used to improve the Internet, Kleinberg is relating this information to how people use the Web. "As people close in on good information, are they actually making use of the cues that are available?" he said.
Kleinberg's work was funded by the National Science Foundation, the Office of Naval Research, and The David and Lucile Packard Foundation.
Timeline: Now
Funding: Government, Private
TRN Categories: Networking
Story Type: News
Related Elements: None
Advertisements:
September 6, 2000
Page One
Nano-scale jets possible
Software squeezes 3-D data
DNA strands form nano-machine
Scaled links make nets navigable
Magnetic interface photographed
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
