stays small world
Technology Research News
The challenge to keeping information flowing
smoothly over the Internet is being able to identify what affects the
flow of data packets and how this will change as the Web grows. Only then
can you plot the most efficient way to direct Net traffic.
This is harder than it sounds. The way traffic is routed on the Internet
today is not as precise as it could be because live tests on such a large
network are difficult
and expensive, and it is difficult to simulate all the variables of networks
as complicated as the Internet.
Researchers from Stanford University, however, have found a way to more
closely simulate the way information flows over these types of networks.
And in looking at the simulations they found good news -- there are potentially
more efficient ways to route traffic over the Net, especially as it grows
larger. The simulations also shed some new light on the principles behind
the classic six-degrees-of-separation experiment.
The Stanford simulation algorithm took into account the scale-free, or
power law nature of the Web; its small-world, or clustering nature; and
a trait known as short path links. In scale-free, or power-law networks,
a few nodes have many links to other nodes, while many nodes have only
a few links. In clustering networks, the relationships among nodes are
not randomly distributed, but are grouped. Short path links means there
are some very short paths sprinkled throughout the network that may directly
link one group to another.
Previous algorithms have allowed researchers to simulate scale-free networks
and small-world networks with short path links, but not networks that
harbor all three traits. There are many natural networks that exhibit
all three traits, including social networks that describe relationships
among groups of people, and metabolic networks that describe things like
the substances a cell uses in life processes.
The researchers found that as networks that harbor all three traits grow
very large, they become very efficient in the number of steps, or hops
a data packet takes to get from one node to another node. "Surprisingly
it took a far shorter number of steps for a scale-free small world than
for a traditional small world," said Amit Ram Puniyani, a physics graduate
student at Stanford University.
While the average number of hops grew from 10 for a 10,000-node network
to 200 for a 100-million-node network in networks that were scale-free
or small-world, the number of average hops grew much more slowly in networks
that were both scale-free and small-world, said Puniyani. The number of
steps grew "logarithmically with the size of the network, which means
that for 10,000 nodes you need five steps, [but] for 100 million the number
grew only to 6.5," he said.
This relationship may also explain the reason behind the six degrees of
separation found by the classic Milgram experiment, Puniyani said. In
the mid-60s, when the population of the United States numbered around
190 million, social psychologist Stanley Milgram asked people living in
Omaha, Nebraska to pass messages to a target person in Boston through
a chain of acquaintances. People receiving the letters sent them to an
acquaintance who was most likely to lead to the target. "Milgram found
that it took an average of six steps for the letters to reach the target.
We believe we have explained this mysterious number," Puniyani said.
The models for networks that were scale-free or small-world, but not both,
predicted an average of more than 200 steps for a letter to find the target
person in a network as large as the relationships among all the people
in the U.S. The researchers' logarithmic growth curve, however, more closely
matches Milgram's empirical evidence that an average of only six hops
was needed for information to get from one node to another in a 190-million
The work is extremely relevant and the method appears particularly efficient
and fast, said Alessandro Vespignani, a research scientist at Abdus Salam
International Centre for Theoretical Physics in Italy. "The search algorithm
is especially devised for scale-free networks and uses their wildly fluctuating
connectivity to speed up the search time. This is both novel and interesting,"
The significance of the research is it shows how data can be sent from
one place to another in a relatively short period of time without having
to know the whole path the data must travel, Vespignani said. In large
networks like the World Wide Web, the path a given piece of data must
traverse to reach its destination can be incredibly complex, he said.
The researchers algorithm has many potential uses, Vespignani said. "The
algorithm could be useful in a huge number of tech applications, especially
in [optimizing] addressing and searching times on the Internet and the
World Wide Web. In principle this could lead to new routing procedures
for sending data to Internet addresses," he said.
The researchers are working on making the model more realistic by adding
differential clustering, said Puniyani. Differential clustering would
add to the model the complexity that "the probability of linking between
two nodes decreases as the distance along the ring [of neighbors] increases,"
In a social network, for example, this would take into account the lesser
probability that an American has acquaintances in Australia than in America,
and the increasing probabilities that a person knows someone who lives
in the same city, works in the same office or lives in the same neighborhood.
"This would make the whole thing much more realistic and appropriate for
simulations," said Puniyani.
The existing algorithm can be used for evaluating the efficiency of traffic
routing algorithms and for doing more realistic modeling in areas like
epidemiology and economics, Puniyani said.
Puniyani's research colleagues were Rajan M. Lukose and Bernardo A. Huberman
of Hewlett-Packard's HP Labs. The research was funded by the National
Science Foundation (NSF).
TRN Categories: Networking; Internet
Story Type: News
Related Elements: Technical paper, "Intentional Walks on
Scale Free Small Worlds," posted on the Los Alamos archive (arXiv) at
Internet stays small world
Tools automate computer
Nanotube kinks control
Hydrogen chip to fuel
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link