Internet remains small world

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 person network.

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," he said.

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," he said.

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).

Timeline:   Now
Funding:   Government
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 http://arXiv.org/abs/cond-mat/0107212.