How to control complex networks

May 12, 2011 by Anne Trafton
MIT and Northeastern University 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 that can analyze any type of — 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 the cover story in the May 12 issue of 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 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 percent. For dense networks — such as neuronal networks — it’s more like 10 percent.

The paper, a collaboration with Albert-Laszlo Barabasi and Yang-Yu Liu of Northeastern University, 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 University. 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.


This story is republished courtesy of MIT News (web.mit.edu/newsoffice/), a popular site that covers news about MIT research, innovation and teaching.

Explore further: Earthquake simulation tops one quadrillion flops

Related Stories

Explained: Ad hoc networks

Mar 10, 2011

In recent years, many network scientists have turned their attention away from centralized networks — such as the Internet and the cell-phone network -- and toward ad hoc networks, wireless networks formed ...

Neuro-tweets: #hashtagging the brain (w/ video)

May 09, 2011

(Medical Xpress) -- We like to think the human brain is special, something different from other brains and information processing systems, but a Cambridge professor set out to test that assumption – by ...

Quantum Communication in Random Networks

May 26, 2010

Internet, networks of connections between Hollywood actors, etc, are examples of complex networks, whose properties have been intensively studied in recent times. The small-world property (that everyone has ...

Recommended for you

Dish Network denies wrongdoing in $2M settlement

7 hours ago

The state attorney general's office says Dish Network Corp. will reimburse Washington state customers about $2 million for what it calls a deceptive surcharge, but the satellite TV provider denies any wrongdoing.

Yahoo sees signs of growth in 'core' (Update)

7 hours ago

Yahoo reported a stronger-than-expected first-quarter profit Tuesday, results hailed by chief executive Marissa Mayer as showing growth in the Web giant's "core" business.

Intel reports lower 1Q net income, higher revenue

7 hours ago

Intel's earnings fell in the first three months of the year amid a continued slump in the worldwide PC market, but revenue grew slightly because of solid demand for tablet processors and its data center services.

Earthquake simulation tops one quadrillion flops

9 hours ago

A team of computer scientists, mathematicians and geophysicists at Technische Universitaet Muenchen (TUM) and Ludwig-Maximillians Universitaet Muenchen (LMU) have – with the support of the Leibniz Supercomputing ...

Twitter buys data analytics partner Gnip

10 hours ago

Twitter says it has bought its data partner Gnip, which provides analysis of the more than 500 million tweets its users share each day—to advertisers, academic institutions, politicians and other customers.

User comments : 3

Adjust slider to filter visible comments by rank

Display comments: newest first

antialias
not rated yet May 12, 2011
This seems universally applicable. Extremely interesting.

Maybe one could use this in reverse to pare down the amount of nodes needed when constructing a network.

denschmitz
not rated yet May 12, 2011
"You have to love these guys at MIT giving me another tool to control the world with."

-- mark zukerburg
Beard
not rated yet May 15, 2011
I hope this helps brain simulations.

More news stories

Intel reports lower 1Q net income, higher revenue

Intel's earnings fell in the first three months of the year amid a continued slump in the worldwide PC market, but revenue grew slightly because of solid demand for tablet processors and its data center services.

Low Vitamin D may not be a culprit in menopause symptoms

A new study from the Women's Health Initiative (WHI) shows no significant connection between vitamin D levels and menopause symptoms. The study was published online today in Menopause, the journal of The North American Menopa ...

Astronomers: 'Tilt-a-worlds' could harbor life

A fluctuating tilt in a planet's orbit does not preclude the possibility of life, according to new research by astronomers at the University of Washington, Utah's Weber State University and NASA. In fact, ...