Nature, Vol 473, Pages 167–173 (12 May 2011)
http://www.barabasilab.com/pubs/CCNR-ALB_Publications/201105-12_Nature-TamingComplexity/201105-12_Nature-paperwcover.pdf
Controllability of complex networks
Yang-Yu Liu,
Jean-Jacques Slotine
& Albert-László Barabási
Abstract
The ultimate proof of our understanding of natural or technological
systems is reflected in our ability to control them. Although control
theory offers mathematical tools for steering engineered and natural
systems towards a desired state, a framework to control complex self-
organized systems is lacking. Here we develop analytical tools to
study the controllability of an arbitrary complex directed network,
identifying the set of driver nodes with time-dependent control that
can guide the system’s entire dynamics. We apply these tools to
several real networks, finding that the number of driver nodes is
determined mainly by the network’s degree distribution. We show that
sparse inhomogeneous networks, which emerge in many real complex
systems, are the most difficult to control, but that dense and
homogeneous networks can be controlled using a few driver nodes.
Counterintuitively, we find that in both model and real systems the
driver nodes tend to avoid the high-degree nodes.
The summary of this paper in Science magazine was clearer, imo:
Science 13 May 2011:
Vol. 332 no. 6031 p. 777
Scientific Link-Up Yields ‘Control Panel’ for Networks
Adrian Cho
In principle, scientists could control the worm Caenorhabditis elegans
as if it were a robot by tapping into the creature's 297 nerve cells—
as some are trying to do. The neurons switch one another on or off,
and, making 2345 connections among themselves, they form a network
that stretches through the nematode's millimeter-long body. How many
neurons would you have to commandeer to control the network with
complete precision? The answer is 49. And the algorithm that made that
tally marks a key advance in the young field of “network science,”
researchers say.
Taking a connect-the-dots approach, researchers have modeled groups of
friends, stock markets, the Internet, and countless other systems as
networks of points, or “nodes,” linked by their interactions. Most
research has focused on characterizing different types of networks and
their behavior. But physicists Yang-Yu Liu and Albert-László Barabási
of Northeastern University in Boston, and engineer Jean-Jacques
Slotine of the Massachusetts Institute of Technology in Cambridge,
have gone further, taking a step toward manipulating networks.
The trio has found a way to determine the smallest number of nodes
that must be externally controlled to force a given network from any
initial state to any desired final state. That number can be
calculated by brute force, but the size of the computation grows
exponentially with the number of nodes. So the researchers take a more
efficient tack, as they report this week in Nature. For each node in a
network, they randomly erase all but one outgoing link and all but one
incoming link to create a skeleton called a “matching.” They apply a
simple technique to make sure the matching contains as many links as
possible. In the end, some nodes are left disconnected. And those
nodes form a set that can control the original network.
The researchers counted the number of control nodes in 37 real-world
networks, including social networks among prison inmates and wiring
diagrams of electronic chips, and unearthed some surprises. The number
of control nodes doesn't depend on how a network is wired, for
example, and the nature of the interactions isn't very important,
either. What matters most is a statistical measure of how many nodes
have different numbers of incoming and outgoing links, the “degree
distribution.”
The work is both more general and more practical than earlier efforts
to apply control theory to networks, says Guanrong Chen, an electrical
engineer at City University of Hong Kong. Previous studies, he says,
dealt only with “undirected” networks: special cases in which if node
A influences node B, then node B must influence node A in the same
way. The new work treats the more-common case of directed networks, in
which A can influence B without B influencing A. Also, Chen says, the
algorithm for finding a set of control nodes “is very important
because it's useful.”
The algorithm might help decipher the networks of biochemical
interactions within cells, says Rune Linding, a biologist at the
Technical University of Denmark in Lyngby. In kinase phosphorylation
networks, proteins called kinases attach phosphate groups to one
another to alter their functions. Human cells contain more than 500
kinases with more than 200,000 phosphorylation sites. Biologists have
traced those interaction networks but don't know how to control them,
Linding says. “We've really been lacking a framework with which to
derive this from data and not from wishful thinking,” he says. “This
paper gives us a framework to go forward.”
Even so, the paper has its limitations. For example, it doesn't
explain how to manipulate the control nodes to get from one state to
another. That likely would depend on the details of connections and
interactions in the network, says Steven Strogatz, an applied
mathematician at Cornell University. “I feel that there is a lot
missing between ‘controllable in principle’ and ‘controllable in
practice,’” he says.
Still, the paper is important, Strogatz says, and so is the
collaboration that produced the results. Twenty years ago, physicists
and control theorists locked horns over the study of chaos, he says,
as the two groups sometimes ignored or dismissed each other's
contributions. “What's really appealing about this paper is that Jean-
Jacques Slotine is a topflight control theorist, and [in Barabási]
he's teamed up with one of the leading network theorists,” Strogatz
says. In other words, the paper itself has forged a network among
fields.
My comments: This paper gives us new, deep, understanding of
networks. Furthermore, it shows that not all seemingly intractable
problems must remain that way.
Edward
--
You received this message because you are subscribed to the Google Groups
"leo-editor" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/leo-editor?hl=en.
