Motifs
distinguish networks
By
Kimberly Patch,
Technology Research NewsThere are many types of networks in the world -- computer webs like the Internet, connections among components in electronics, relationships among friends and acquaintances, transportation grids, food relationships among animals, connections among neurons, and interactions among genes.
Scientists from the Weizmann Institute of Science in Israel and Spring Harbor Laboratory have shown that it is possible to categorize networks by looking at certain recurring circuits, or motifs, within the networks. "The motifs are small, local, wiring patterns that occur throughout the network," said Uri Alon, a senior scientist at the Weizmann Institute of Science.
Identifying and examining these motifs can help explain how networks function, Alon said. "The motifs allow us to break up the network into building blocks," he said. "This gives the hope that understanding the function of each motif would allow us to build up an understanding of the entire network behavior," he said.
Understanding network motifs could contribute to better Internet search engines, a better understanding of networks within cells, which could help in curing disease, and a better understanding of social networks, which could help heal societal rifts.
Each type of network appears to have its own characteristic set of motifs, said Alon. "This is probably because they are functional units important to whatever function the network was designed or evolved to perform," he said.
The feedforward loop, or filter motif, for example, is common in networks of neurons, but is relatively rare and therefore not a motif in food webs, said Alon. A feedforward loop consists of network nodes x, y and z, in which x has connections to y and z, and y also has a connection to z. In food webs, where nodes are animals, this pattern is carried out only by omnivores (x) that both eat another animal (y) and the food (z) that that animal eats, he said.
The researchers' work is complementary to a line of research that looks for broad patterns across networks. That line of research has shown, for example, that many networks, including the Internet, have scale-free and small-world attributes.
Scale-free networks contain a few nodes that link to many other nodes, and many nodes with few links. Small-world networks contain short paths between large nodes, allowing the networks to be traversed using fewer hops between nodes; this broad pattern appears across social networks and the Internet and is responsible for the well-known six-degrees-of-separation effect.
To find the network motifs, the Weizmann researchers compiled databases of networks, including all known transcription interactions in bacteria, and wrote algorithms that analyzed information. "We had to make up efficient algorithms that [could] handle networks with millions of nodes and count their subgraphs," or repeating connection patterns, he said.
Transcription occurs whenever a cell needs to make a protein. Transcription molecules, which are also proteins, direct the copying of a portion of DNA that provides a physical blueprint for the needed protein.
The researchers' approach showed that groups of networks share certain motifs. "For example, seven different food webs share the same two motifs," Alon said. Those motifs are a chain, where one type of prey eats another, which eats another, and a diamond-shaped pattern, where one type of prey eats two others, which both eat a fourth type of prey.
These motifs are very different from those that occur in biochemical networks, which share the feedforward loop and a bi-fan pattern, where x and y can each transmit information one-way to z or w, according to Alon.
And "these are again different [from] the motifs found in the World Wide Web," Alon said. The researchers found five motifs in the Web: a fully-connected triangular relationship that shows two-way connections among x, y, and z; a modified feedback loop where there are two-way connections between x and y, and y and z, but a one-way relationship from z to x; and three increasingly less-connected relationships.
A modified feedback loop appears on the Web when there is a two-way link between a university homepage (x) and a department page (y), a two-way link between a department page (y) and a lab page (z), but, because the university does not have room to list all the labs in its homepage, only a one-way link from z to x.
The presence of many two-way connections in the Web may reflect a design weighted toward providing short paths between related pages, according to Alon.
The researchers also found that networks that perform information-processing share similar motifs, even if those networks are otherwise quite different, according to Alon. "Sometimes two networks from completely different fields, made up of completely different elements, show the same motifs," said Alon. "This occurs, for example in transcription networks and neuron networks, even though one describes proteins and genes within a yeast cell, and the other describes neuron wiring in a worm," he said.
The similarity in motifs probably reflects a fundamental similarity in the design constraints of the two types of networks, according to Alon. Both types of networks carry information from sensory components to components that carry out a task. In a transcription network, transcription proteins regulated by biochemical signals communicate with genes that build proteins; in a neural network motor neurons transmit signals to muscles.
One possible function of this type of motif is to activate output only if the input signal is persistent, and to allow a rapid deactivation when the input goes off, according to Alon.
The researchers also found that human engineering uses design rules similar to those used by evolution, said Alon. "Both converge again and again on a small set of useful circuits" or motifs, he said. "Electronic chips are built of recurring circuits such as operational amplifiers and filters. Engineers love to use these elementary circuits because they are robust and... plug-and-play. Evolution did not go to engineering school, and yet still uses similar design principles," he said.
The network motifs should provide strong clues about what makes a complex network tick, said Alon. For example, the feedforward loop and amplifier motifs of biological networks will be very useful for designing nanoscale devices that need to compute, he said. "The circuits favored by biology will be the ones that work [well in] engineering on the nanoscale," he said.
In computer science, understanding the basic recurring structure of the Web may contribute to better ways to search and design networks.
And in medicine, the hardest diseases to cure have to do with networks -- the forces governing when a cell divides and when it dies, for instance, said Alon. "Doctors attempting to fix the cell are working today without a blueprint of its networks," he said.
More information about networks could even help heal societal rifts, he said. "Working in Israel, one hopes that understanding the basic elements of social networks may one day work to heal the cycles of violence that occur in societies and nations," he said.
The researchers work is interesting because "it tries to make connections between the different types of complex networks beyond the power-law results that we have seen thus far," said Filippo Menczer, an assistant professor of management services at the University of Iowa. "It goes beyond global link analysis such as the studies which unveiled the scale-free/power degree distribution of many complex networks including the Web, and starts focusing on more local structures," he said
The work suggests that the very small patterns of connectivity that appear much more or much less frequently than you'd expect in random networks must serve some purpose, said Menczer. "The patterns found for the Web [, however,] are not too surprising and may [simply] reflect common behaviors of authors' linking to related pages," he said.
If the method can be applied to larger motifs, it could shed light on unknown functional mechanisms of networks, Menczer added.
The method can be applied to any network now, Alon said.
The researchers' are working on extending the method to analyze cell-wide biochemical networks, said Alon. "We would like to obtain the concepts and tools needed to build a blueprint of a cell," he said.
They are also working on figuring out why certain types of motifs appear in some networks but not others. "Can we divide the world of networks into universal classes, each optimized to perform different tasks?" said Alon. "The far-off goal is to reach a unifying theory of evolved and designed" networks, he said.
Alon's research colleagues were Ron Milo, Nadav, Kashtan, Shalev Itzkovitz and Shai Shen-Or at the Weizmann Institute of Science, and Dmitry Chklovskiie at Cold Spring Harbor Laboratory. They published the research in the October 25, 2002 issue of the journal Science. The research was funded by the Israel Science Foundation, The Human Frontiers Science Foundation and the Minerva Foundation.
Timeline: Now
Funding: Government, Private
TRN Categories: Physics; Internet
Story Type: News
Related Elements: Technical paper, "Network Motifs: Simple Building Blocks of Complex Networks," Science, October 25, 2002.
Advertisements:
November 27/December 4, 2002
Page One
Molecule stores picture
Fast quantum crypto demoed
Software system heals itself
Motifs distinguish networks
Oxygen makes nanotube memory
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.
