Disappearing
links shape networks
By
Kimberly Patch,
Technology Research NewsIt is fairly obvious that networks are a common ingredient in social circles, biological processes and computer communications. What is much less apparent is exactly how the different aspects of these networked systems interact to direct network growth.
Researchers are delving deeply into network dynamics to try to tease out what makes a difference in the growth of things like working relationships among actors, connections among biological processes in cells, and links among Web pages on the Internet.
A better understanding of these relationships promises to help the Internet grow more smoothly and may make mobile networks like those of cellphones easier to manage.
One common ingredient in many large networks is a scale-free, or power-law structure. In scale-free networks, a few nodes have a lot of connections to other nodes, and many nodes have only a few connections each. Previous research has shown that this structure can be caused by a sort of perpetual rich-get-richer dynamic that says the larger a node is, the more likely it is to attract links.
A theoretical physicist from St. Petersburg State University in Russia has found that this common network structure may also be maintained by a different dynamic. Her disappearing link model shows that under certain conditions the rate of appearance and disappearance of links in a network may also cause a scale-free structure.
The research also shows that the rate of appearance and disappearance of links is probably more important to the dynamics of the network then the size of the network.
In real-world networks like human social circles and the Internet, the dynamic of links disappearing is common, but this dynamic is often absent in research studies of networks, said Olga Kirillova. Investigations of how significant "the maximum number of possible arising and disappearing links is [are] practically absent," she said.
Events like movie actors fading away and Web pages doing the same may be important to network structure, according to Kirillova. In real communication networks there are phenomena such as species extinction, aging and death, she said. These changes don't just simply subtract a node from the system; they also change the network's structure of interactions, she said.
Kirillova's research showed that when the number of links appearing and disappearing was set at about 0.5 percent of the network, the network was pushed toward a scale-free structure. The rates of link appearance and disappearance in both the Internet and in the network of scientific paper citations fall close to this number, according to Kirillova.
The model is a valuable one that may bear on several types of real world networks, said Bosiljka Tadic, a theoretical research scientist at the Jozef Stefan Institute in Slovenia. "In particular, it may be useful for closed communities and on a relatively small time scale. For instance, [biological] food chains and commercial supply networks... may be sensitive to fluctuations of links. Cutting a link or adding new link may trigger a cascade of link updates," he said.
A big question is why so many networks have a scale free structure, "because we seem to see it everywhere," said Jon Kleinberg, an associate professor of computer science at Cornell University. "The question is what is the... basic mechanism at work that's causing all these networks to have this power-law structure," he said.
Kirillova's research says if you "correlate the appearance and disappearance just right you get this power-law behavior even if you don't have a rich-get-richer kind of process," said Kleinberg. "This is yet another way to see power-law" type networks arising.
In the end, the problem of network structure is getting "more challenging because it isn't that there is somehow a single explanation" of the scale free structure, said Kleinberg. "It's completely conceivable that they are arising in different situations for different reasons." This, in turn, raises an important issue, he said. "When we see a power-law [structure], how do we decide... which model... is really the best approximation?"
Kirillova's model may have a significant role in exploring the behavior of wireless networks, whose links appear and disappear fairly quickly, Klineberg added.
Network models may also provide insight into biological evolution, said Kirillova. One of the most important aspects of evolution is that useful structures like limbs and organs emerge through slow improvements that are sparked by random genetic changes and limited by the laws of physics. Understanding the emergent, dynamic structure of networks, which also harbor local rules that govern changes, may eventually help us better understand biological evolutionary processes, she said.
Kirillova published the research in the August 6, 2001 issue of Physical Review Letters. The research was funded by St. Petersburg State University.
Timeline: Now
Funding: University
TRN Categories: Networking; Internet
Story Type: News
Related Elements: Technical paper, "Communication Networks with an Emergent Dynamical Structure," Physical Review Letters, August 6, 2001.
Advertisements:
November 14, 2001
Page One
Crossed nanowires compute
Disappearing links shape networks
Stored light altered
Flipping flakes change color
Evolution optimizes satellite orbits
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.
