show six degrees of separation
Technology Research News
The circuits that make up computers, the
computers that make up the Internet, and the people that make up a country
have something in common: six degrees of separation.
Complicated networks like the Internet
and social circles share several traits, including the ability to
transmit information from one node to any other node in six or fewer steps,
or hops between neighboring nodes.
A team of researchers from Spain and the U.S. has found that this small-world
trait also exists in networks of computer circuits.
Pages on the Internet are connected with hyperlinks.
People in a social network are linked because they know each other. In
an electronic device a link exists if two elements are physically connected.
The small-world trait found in all three of these types of networks allows
information "to transfer very quickly since a small number of jumps connects
any two elements," said Ricard Solé, a professor at the Technical University
of Catalonia in Spain and an external professor at the Santa Fe Institute.
circuits, like these other complicated networks, are also scale-free,
meaning they consist of a few nodes, or components with many connections
and many nodes with just a few connections, according to Solé.
The findings could point to ways of designing circuits that fail less
often -- an important trait for systems used in, for instance, space exploration.
The work also emphasizes a trend -- researchers are finding patterns like
these in many places. "We look for patterns in complex networks, both
natural and artificial in order to see if universal [patterns] are present,"
Electronic circuits were a good place to look because they include intrinsic
features that result from conflicts between the needs for low-cost and
high performance, said Solé. "Something like that also occurs in natural
systems," where systems compete for survival over time, he said.
The researchers analyzed electronic circuits ranging from an old television
made up of resistors, capacitors and diodes soldered together on a circuit
board to a digital microchip containing thousands of components. What
they found is that as circuits get larger, they look more like the Internet.
"There is a pattern of organization in real circuits that reveals a process
of optimization as circuit complexity increases," said Solé.
Although circuits are designed to be efficient, "interestingly, there
is another feature that has not been designed and that is also present,"
said Solé. The scale-free structure, with most components having just
a few links to other components and a few components having many links
is not designed consciously, he said.
In studies of scale-free node distribution in the Internet, researchers
have found its consequence: "the Internet is extremely resilient to removal
of randomly chosen nodes, but very fragile when highly-connected nodes
are attacked," said Solé.
More fault-tolerant circuits can be designed by taking advantage of global
attributes like small-world connections and scale-free distribution, he
said. "A standard device will, of course, fail if a single unit fails,
but a new generation of adaptive configurable circuits might take advantage
of these properties in order to reach very high levels of stability against
random failures," he said.
Fault-tolerant traits are especially needed in circuitry that is difficult
to fix or replace, like that used in space exploration, he added.
There are many examples of small-world behavior in nature, said Hawoong
Jeong, an assistant professor of physics at the Korean Advanced Institute
of Science and Technology. "It is not surprising, but it is interesting
to know that electronic circuits also show such behavior," he said.
Natural systems evolve toward small-world networks because they have "extreme
failure tolerance," and toward scale-free networks because they "use resources
more efficiently compared to random networks," said Jeong.
The study is part of a trend toward uncovering more examples of network
traits. What is needed next is is a deeper examination of the dynamics
of these systems, he said.
The researchers are currently exploring exactly how these global topological
patterns can be used to optimize circuit performance, including the implications
for adaptive computing, said Solé. The work could affect circuit design
ideas within a few years, he said.
Solé's research colleagues were Ramon Ferrer i Cancho and Christiaan Janssen
of The Technical University of Catalonia. They published the research
in the October, 2001 issue of Physical Review E. The research was funded
by the Santa Fe Institute.
Timeline: 3 years
TRN Categories: Integrated Circuits; Networking
Story Type: News
Related Elements: Technical paper, "Topology of Technology
Graphs: Small World Patterns in Electronic Circuits," physical review
E., October 2001.
Chemists create nano
English could snowball
Page age shapes Web
six degrees of separation
Spot of gold makes
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link