Controllability of complex networks
Last post I mentioned a paper by Liu, Slotine and Barabási about Controllability of Complex Networks published on Nature few days ago. Here are some notes from ScienceNews:
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.
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.