It’s like a Hollywood political thriller come true: a handful of people lurking in the shadows, controlling the minds of millions. New research reveals that it’s possible for a few individuals to enslave an entire network, even if they aren’t highly connected themselves.
Scientists have figured out how to identify the nodes — the points that link to other points in a network — that when tweaked can control the entire network. The research, published in the May 12 Nature, might lead to more secure power grids, tricks for controlling the metabolic processes of cells and marketing campaigns that spread like the plague.
If you wanted to nudge people on a social network into trying a new product or get a biochemical system to turn compound A into compound B, you could just push your product or compound into every entry point in the network. But that’s sort of a silly approach, says study coauthor Jean-Jacques Slotine of MIT. A much more efficient tactic would be to target just the nodes needed to get the desired outcome.
So, along with colleagues Albert-László Barabási and Yang-Yu Liu of Northeastern University in Boston, Slotine developed an algorithm that calculates the minimum number of these driver nodes and finds them. Then the researchers asked how much this minimum number depended on the architecture of the network — be it a tidy grid or a convoluted web — and how much it depended on connectivity — whether each node was linked to a lot of other nodes or just a few.
Oddly, a network’s layout barely mattered. The number of nodes needed to control a whole network mostly depends on the average number of connections per node, the researchers found. Sparse networks, such as the regulatory system controlling genes in a yeast cell, are pretty resistant to control; roughly 80 percent of the nodes need to be influenced to get the desired outcome. Dense networks, on the other hand, such as many social networks, were much easier to control: Influence roughly 20 percent of the nodes and the whole network responds.
“I found that very shocking,” says Magnus Egerstedt, director of the Georgia Robotics and Intelligent Systems Laboratory at Georgia Tech. “Social networks, which seem to be these random, ad hoc collections of people freely expressing information and sharing their thoughts — those were much easier to control than other networks.”
Another counterintuitive finding that emerged is where those power nodes lie. The nodes to tweak aren’t the hubs with many, many connections, but unassuming nodes off to the side.
“It’s a little scary,” says Slotine. “Do we really want large groups of people whose opinions are going to be controlled by just a few? And not the obvious people?”
Knowing that highly connected nodes aren’t the power players is a big step toward understanding why complex systems often behave nonsensically, says Dirk Helbing of the Swiss Federal Institute of Technology Zurich. “They often behave in a counterintuitive way. Making sense of complex systems and managing them requires thinking out of the box and using new tools,” he says.
The new math also allowed the researchers to determine a network’s robustness and its vulnerabilities. Removing some links between nodes has little effect, while knocking out others drastically alters flow. The ability to pinpoint crucial links might help researchers find an infectious bacterium’s Achilles’ heel or help engineers shore up power grids.
“It gives us a better idea how to tame complex systems, particularly where we face serious coordination failures,” says Helbing. Take traffic, for example. “Traffic light optimization is a damn hard problem, which cannot be perfectly done in real time today, not even with supercomputers. Knowing which nodes we must focus on will allow us to fight traffic congestion more efficiently.”
Other researchers aren’t so sure that the math can be applied as widely as it seems. While the findings may hold for viral marketing in a social network, some networks are more complicated and maybe the same broad brush doesn’t apply, says networks expert Ali Jadbabaie of the University of Pennsylvania. There’s more low-level detail in a power grid than in a social network, he says. “Sometimes low-level details don’t matter, but sometimes they do,” says Jadbabaie. “This is interesting, with caveats.”
But researchers generally agree that the work advances the general understanding of how networks behave, a problem that humans, who often think hierarchically, seem to have a hard time with.
“We have very poor intuition about dynamic networks,” says Egerstedt, a control theory expert whose projects include how to manipulate swarms of mosquito-sized robots for environmental monitoring or intelligence gathering. “We are still so bad at driving lots of robots into a formation. I was trying to think of one thing in life where we have that kind of control, and the only thing I could think of is sheepherding. We have sheepherder dogs — driver nodes which are pretty good at controlling the herd with the help of a few leader female sheep. But that’s about as far as our intuition goes.”
Back Story | Robot Army
An automated army invades a conference room at Georgia Tech. Researchers there are investigating ways of creating networks to control swarms of robots.
Credit: Jean-Pierre de la Croix
Controlling whole swarms of robots is one of the great challenges of robotics — and one that researchers have not yet mastered. Much of the difficulty stems from the complexity of the situation: many individuals, each with their many gears and parts, acting according to their own dynamics and connected to other agents that are all doing the same. To get a swarm to act in a coordinated way, the individual robots need to be linked in networks.
But just as everybody on a conference call can’t talk at once, the network has to be configured so the most valuable information gets distributed widely while meaningless chatter is swept aside. Imagine a squadron of drones flying over enemy terrain — a single human operator can’t direct dozens of aircraft simultaneously. The network has to be set up so that some drones can order their compatriots into action in the most effective way. In other words, it needs driver nodes.
Using an algorithm developed by researchers at MIT and Northeastern University, a dense network might be controlled by 20 percent of its nodes. But to coordinate a swarm taking incoming fire, you’d have to do way better than that. Today, says Magnus Egerstedt of Georgia Tech, a single drone flying over Afghanistan might have four or five human operators: “We want to invert that,” Egerstedt says.
