Networks Dominated By Rule of the Few

Social hubs like Facebook, can be directed from relatively few control points.

+ More

By Rachel Ehrenberg, Science News

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.”