links shape networks
Technology Research News
It 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
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,
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.
TRN Categories: Networking; Internet
Story Type: News
Related Elements: Technical paper, "Communication Networks
with an Emergent Dynamical Structure," Physical Review Letters, August
Crossed nanowires compute
Stored light altered
Flipping flakes change
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link