Failures in large networks can be prevented with local focus

We live in an increasingly connected world, a fact underscored by the swift spread of the coronavirus around the globe. Underlying this connectivity are complex networks — global air transportation, the internet, power grids, financial systems and ecological networks, to name just a few. The need to ensure the proper functioning of these systems also is increasing, but control is difficult.

Now a Northwestern University research team has discovered a ubiquitous property of a complex network and developed a novel computational method that is the first to systematically exploit that property to control the whole network using only local information. The method considers the computational time and information communication costs to produce the optimal choice.

The same connections that provide functionality in networks also can serve as conduits for the propagation of failures and instabilities. In such dynamic networks, gathering and processing all the information necessary to make a better decision can take too much time. The goal is to diagnose a problem and take action before it leads to a system-wide issue. This may mean having less information but being timely.

“Control is about getting the most relevant information and then making the best decision promptly,” said Adilson E. Motter, an expert in complex systems and nonlinear dynamics. “We found that no matter how large the network is, it can often be treated as a small or local network for the purposes of control. We call this property locality, and most networks have it. Understanding this network property is key to effectively and efficiently controlling the system.” 

Motter, who supervised the research, is the Charles E. and Emma H. Morrison Professor at Northwestern’s Weinberg College of Arts and Sciences. His research focuses on the network modeling and control of complex physical, biological and engineered systems.

An important feature is that the method can be applied broadly across different types of network systems to control the system when perturbed, Motter said. In their study, the researchers demonstrate the effectiveness of their method through four concrete examples, including the reduction of epidemic spread through the global air transportation network and the stability control of the Eastern U.S. power grid.

A paper describing the researchers’ theory and algorithms was published recently in the Proceedings of the National Academy of Sciences (PNAS). 

How the method works

Motter describes their approach as similar to a fill-in-the-blank problem where you are asked to guess a certain word in a sentence of blank words. It is very hard to guess without being given other words. If you are given a word next to your blank, your chance of guessing correctly is better. And your chances increase when given more words in the neighborhood of the word you are asked to guess. 

“Suppose you want to guess the word with a 99% chance of getting it right, so you ask, ‘What is the minimum number of other words I need to know and where should they be located?’” said Motter, who is a member of the Northwestern Institute on Complex Systems (NICO). “That’s how we approached this study. We want to have the optimal set of points in the network to measure and base our decision on. It’s not very practical to develop a method that relies on knowing everything that’s happening everywhere.”

Real networks are nonlinear

Previous and recent research on network control done in the network science community has focused mainly on linear models because, in principle, it is much simpler to manipulate linear dynamics. The challenge, however, is that real networks are nonlinear.

Key to the new method is the researchers’ accounting of this nonlinear nature of the dynamics in real networks. In such systems, the size of the response is generally not proportional to the size of the disturbance. This can be a blessing in disguise, as small control interventions can lead to a ripple effect that propagates through the network, rescuing or reprogramming it.

“Nonlinearity means that trouble grows disproportionately, but so can remedy, if suitably applied,” Motter said. “We wanted to address the nonlinear response of large-scale systems, and the method we developed does just that while relying exclusively on local connections. This makes it applicable to virtually any network.”

The U.S. Combat Capabilities Development Command’s Army Research Laboratory (grant W911NF-19-1-0383), Advanced Research Projects Agency–Energy (award DE-AR0000702) and the Institute for Sustainability and Energy at Northwestern (ISEN) supported the research.