New Algorithms Discover Networks Within Systems

Networks – whether biological networks of cells, financial networks of markets, or social networks of friends and colleagues – play a large role in our lives. But understanding and controlling the behavior that emerges from these networks – how a network of neurons generates motor control, for example – remains a big question in the study of complex systems.

An important first step is to be able to reconstruct the topology of networks – for example, which neurons are connected by synapses – which isn’t always clear, especially when the networks change in real time.

Northwestern Engineering researchers have developed two new algorithms that can infer the topology of a network by observing the behavior of the individual nodes (such as neurons) in real time, using fewer measurements and simpler models than previous algorithms.

“Our algorithms offer immediate application to difficult network reconstruction problems,” said Kevin Lynch, professor of mechanical engineering and co-author of the paper. Other authors include Randy Freeman, professor of electrical and computer engineering, and Daniel Alberto Burbano Lombana, a former postdoctoral fellow. The authors are members of the Northwestern Institute on Complex Systems, a hub for pathbreaking research in complex systems and data science.

The results were published in the journal Chaos.

Using adaptive control theory

To understand a network, researchers must understand how the networks’ nodes are connected through links. When the flu spreads each winter, for example, each person is a node, while each interaction they have with another person is a link. Broadly speaking, the researchers hoped to create algorithms that can determine who must be interacting with whom based on the observed progression of the flu.

The researchers approached this problem using adaptive control theory, a subfield of feedback control theory, which is better known for systems such as autopilot and cruise control.

By adapting the general approach to the specifics of network dynamics, the researchers developed two estimator algorithms that reveal the network topology by examining the activity of the nodes.

The first estimator is simpler, but it works only for a particular class of systems. The second is more general but requires more computation to implement.

“Compared to others, our algorithms can accurately estimate the network links with fewer measurements of the nodes using less restrictive models of how the nodes interact with each other,” Freeman said.

Potential applications in robotics

The researchers validated the algorithms in computer simulations and in experiments where they successfully inferred networks of coupled chaotic electrical oscillators (circuits that generate voltage chaotically).

“When you put the oscillators in a network and allow the output of one to influence another, it changes the behavior of the other, and then we can determine how they are connected to each other,” Freeman said.

The success in reconstructing the network among the oscillators shows that the algorithms could have immediate application across a wide range of networks, including financial and biological networks.

Lynch hopes to apply the algorithms to cooperative manipulation by robot swarms. Robot “ants,” for example, could use the algorithms to determine the mechanical properties of an object they are carrying together, helping the ants to better control the object’s motion.

In the future, the researchers plan to study how a network can best be artificially stimulated to expose its topology when nodes are dormant or in a steady state.

“The push is to make these algorithms as broadly applicable as possible, and to minimize the amount of sensing, communication, and computation needed to implement them,” Lynch said.