Gauging the resilience of complex networks
TROY, N.Y. » Whether a transformer catches fire in a power grid, a species disappears from an ecosystem, or water floods a city street, many systems can absorb a certain amount of disruption. But how badly does a single failure weaken the network? And how much damage can it take before it tips into collapse?
Network scientist Jianxi Gao is building tools that can answer those questions, regardless of the nature of the system.
“After a certain point, dam- age to a system is so great that it causes catastrophic failure. But the events leading to a loss of resilience in a system are rarely predictable and often irreversible. That makes it hard to prevent a collapse,” said Dr. Gao, an assistant professor of computer science at Rensselaer Polytechnic Institute, who was awarded a prestigious National Science Foundation CAREER award to tackle the problem. “The mathematical tools we are building will make it possible to evaluate the resilience of any system. And with that, we can predict and prevent failure.”
Imagine the effects of climate change on an ecosystem, Dr. Gao said. A species that can’t adapt will dwindle to extinction, perhaps driving a cascade of other species, which eat the first, to the brink of extinction also. As the climate changes, and more species are stressed, Dr. Gao wants the ability to predict the impact of those dwindling populations on the rest of the ecosystem.
Predicting resilience starts by mapping the system as a network, a graph in which the players (an animal, neuron, power station) are connected by the relationships between them, and how that relationship affects each of the players and the network overall. In one visualization of a network, each of the players is a dot, a node, connected to other players by links that represent the relationship between them — think who eats whom in a forest and how that impacts the overall population of each species, or how information moving across a social media site influences opinions.
Over time, the system changes, with some nodes appearing or disappearing, links growing stronger or weaker or changing relationship to one another as the system as a whole responds to that change.
Mathematically, a changing network can be described by a series of coupled nonlinear equations. And while equations have been developed to map networks in many fields, predicting the resiliency of complex networks or systems with missing information overwhelms the existing ability of even the most powerful supercomputers.
“We’re very limited in what we can do with the existing methods. Even if the network is not very large, we may be able to use the computer to solve the coupled equations, but we cannot simulate many different failure scenarios,” Dr. Gao said.
Dr. Gao debuted a preliminary solution to the problem in a 2016 paper published in Nature. In that paper, he and his colleagues declared that existing analytical tools are insufficient because they were designed for smaller models with few interacting components, as opposed to the vast networks we want to understand. The authors proposed a new set of tools, designed for complex networks, able to first identify the natural state and control parameters of the network, and then collapse the behavior of different networks into a single, solvable, universal function.
The tools presented in the Nature paper worked with strict assumptions on a network where all information is known — all nodes, all links, and the interactions between those nodes and links. In the new work, Dr. Gao wants to extend the single universal equation to networks where some of the information is missing. The tools he is developing will estimate missing information — missing nodes and links, and the relationships between them — based on what is already known. The approach reduces accuracy somewhat, but enables a far greater reward than what is lost, Dr. Gao said.
“For a network of millions or even billions of nodes, I will be able to use just one equation to estimate the macroscopic behavior of the network. Of course, I will lose some information, some accuracy, but I capture the most important dynamics or properties of the whole system,” Dr. Gao said. “Right now, people cannot do that. They cannot test the system, find where it gives way, and better still, improve it so that it will not fail.”
“The ability to analyze and predict weaknesses across a variety of network types gives us a vast amount of power to safeguard vulnerable networks and ecosystems before they fail,” said Curt Breneman, dean of the Rensselaer School of Science. “This is the kind of work that changes the game, and this CAREER award is a recognition of that potential. We congratulate Jianxi and expect great things from his research.”
“CAREER: Network Resilience: Theories, Algorithms, and Applications” is funded with a $576,000 grant from the National Science Foundation.