Circuits show six degrees of separation

By Kimberly Patch, 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.

Computer 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," said Solé.

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
Funding:   Institute
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.


November 21, 2001

Page One

Chemists create nano toolkit

English could snowball on Net

Page age shapes Web

Circuits show six degrees of separation

Spot of gold makes tiny transistor



Research News Roundup
Research Watch blog

View from the High Ground Q&A
How It Works

RSS Feeds:
News  | Blog  | Books 

Ad links:
Buy an ad link


Ad links: Clear History

Buy an ad link

Home     Archive     Resources    Feeds     Offline Publications     Glossary
TRN Finder     Research Dir.    Events Dir.      Researchers     Bookshelf
   Contribute      Under Development     T-shirts etc.     Classifieds
Forum    Comments    Feedback     About TRN

© Copyright Technology Research News, LLC 2000-2006. All rights reserved.