Scaled links make nets navigable

By Eric Smalley, Technology Research News

Actor 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


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


Research News Roundup
Research Watch blog

View from the High Ground Q&A
How It Works

RSS Feeds:
News  | Blog  | Books 

Ad links:
Buy an ad link


Ad links: Clear History

Buy an ad link

Home     Archive     Resources    Feeds     Offline Publications     Glossary
TRN Finder     Research Dir.    Events Dir.      Researchers     Bookshelf
   Contribute      Under Development     T-shirts etc.     Classifieds
Forum    Comments    Feedback     About TRN

© Copyright Technology Research News, LLC 2000-2006. All rights reserved.