MIT and Northeastern Univ. researchers devised a computer algorithm that can generate a controllability structure for any complex network. The red points are ‘driver nodes,’ which can control the rest of the nodes (green). Image: Mauro Martino |
At
first glance, a diagram of the complex network of genes that regulate cellular
metabolism might seem hopelessly complex, and efforts to control such a system
futile.
However,
an MIT researcher has come up with a new computational model that can analyze
any type of complex network—biological, social, or electronic—and reveal the
critical points that can be used to control the entire system.
Potential
applications of this work, which appears as a cover story in Nature,
include reprogramming adult cells and identifying new drug targets, says study
author Jean-Jacques Slotine, an MIT professor of mechanical engineering and
brain and cognitive sciences.
Slotine
and his co-authors applied their model to dozens of real-life networks,
including cell-phone networks, social networks, the networks that control gene
expression in cells and the neuronal network of the C. elegans worm. For each, they calculated the percentage of points
that need to be controlled in order to gain control of the entire system.
For
sparse networks such as gene regulatory networks, they found the number is
high, around 80%. For dense networks—such as neuronal networks—it’s more like
10%.
The
paper, a collaboration with Albert-Laszlo Barabasi and Yang-Yu Liu of
Northeastern Univ., builds on more than half a century of research in the field
of control theory.
Control
theory—the study of how to govern the behavior of dynamic systems—has guided
the development of airplanes, robots, cars, and electronics. The principles of
control theory allow engineers to design feedback loops that monitor input and
output of a system and adjust accordingly. One example is the cruise control
system in a car.
However,
while commonly used in engineering, control theory has been applied only
intermittently to complex, self-assembling networks such as living cells or the
Internet, Slotine says. Control research on large networks has been concerned
mostly with questions of synchronization, he says.
In
the past 10 years, researchers have learned a great deal about the organization
of such networks, in particular their topology—the patterns of connections
between different points, or nodes, in the network. Slotine and his colleagues
applied traditional control theory to these recent advances, devising a new
model for controlling complex, self-assembling networks.
“The
area of control of networks is a very important one, and although much work has
been done in this area, there are a number of open problems of outstanding
practical significance,” says Adilson Motter, associate professor of physics at
Northwestern Univ. The biggest contribution of the
paper by Slotine and his colleagues is to identify the type of nodes that need
to be targeted in order to control complex networks, says Motter, who was not
involved with this research.
The
researchers started by devising a new computer algorithm to determine how many
nodes in a particular network need to be controlled in order to gain control of
the entire network. (Examples of nodes include members of a social network, or single
neurons in the brain.)
“The
obvious answer is to put input to all of the nodes of the network, and you can,
but that’s a silly answer,” Slotine says. “The question is how to find a much
smaller set of nodes that allows you to do that.”
There
are other algorithms that can answer this question, but most of them take far
too long—years, even. The new algorithm quickly tells you both how many points
need to be controlled, and where those points—known as “driver nodes”—are
located.
Next,
the researchers figured out what determines the number of driver nodes, which
is unique to each network. They found that the number depends on a property
called “degree distribution,” which describes the number of connections per
node.
A
higher average degree (meaning the points are densely connected) means fewer
nodes are needed to control the entire network. Sparse networks, which have
fewer connections, are more difficult to control, as are networks where the
node degrees are highly variable.
In
future work, Slotine and his collaborators plan to delve further into
biological networks, such as those governing metabolism. Figuring out how
bacterial metabolic networks are controlled could help biologists identify new
targets for antibiotics by determining which points in the network are the most
vulnerable.