Mathematical Framework that Prioritizes Key Patterns in Networks Aims to Accelerate Scientific Discovery

DARPA researchers successfully demonstrate a scalable, generalized framework designed to generate new insights into the structure and behavior of complex science and engineering systems

Networks are mathematical representations to explore and understand diverse, complex systems—everything from military logistics and global finance to air traffic, social media, and the biological processes within our bodies. In each of those systems, a hierarchy of recurring, meaningful internal patterns—such as molecules and proteins interacting inside cells, and capacitors and resistors operating within integrated circuits—determines the functions or behaviors of those systems. The larger and more intricate a system is, however, the harder it is for current network modeling techniques to uncover these patterns and represent them in organized, easy-to-understand ways.

Researchers at Stanford University, funded by DARPA’s Simplifying Complexity in Scientific Discovery (SIMPLEX) program, have made progress in overcoming these challenges through a framework they have developed for identifying and clustering what mathematicians call “motifs”: essential but often obscure patterns within systems that are the building blocks of mathematical modeling and that facilitate the computational representation of complex systems. A research paper describing the team’s achievement, “Higher-Order Organization of Complex Networks,” was published today in Science: https://ow.ly/oMba3021HT7. At the heart of the team’s success was the creation of algorithms that can automatically explore and prioritize the hidden patterns in data that are fundamental to explaining network structure and function.

“This approach mathematically represents complex networks more efficiently, revealing deeper functional relationships within networks and how each pattern contributes to the whole,” said Reza Ghanadan, DARPA program manager. “Additionally, it provides an analytic, systematic, and scalable way to generate hypotheses that are provably relevant to a given network based on key insights that the patterns reveal in that network. Taken together, this is an exciting demonstration of the promise that motif clustering shows for helping to unravel the complexity of diverse scientific and engineering systems, and for accelerating discovery by highlighting which avenues of research could potentially yield better results.”

As part of their research, the Stanford team tested their motif-clustering framework by applying it to several complex systems, including air traffic routes connecting the 50 most populous cities in the United States and Canada. In that example, the researchers first used conventional network modeling approaches that group cities that are connected, not cities that play similar roles in the network’s structure, such as hubs.

The team then applied the motif-clustering framework, which analyzed the flight data and ranked airports based on their priority as a hub (i.e., the set of routes between two cities always included that airport) and their geographic location. The SIMPLEX algorithms automatically detected the eight largest hubs, demonstrating that the motif-clustering representation accurately captured the nature of the system. The framework shows how the network as a whole organizes around these patterns and provides a metric for how significant a given pattern is to the network structure, enabling users to compare patterns and discover which ones are most significant.

The Stanford team is collaborating with another SIMPLEX research group, based at Baylor University. That group is applying motif clustering to protein networks to help generate hypotheses about how proteins interact in complex biological systems. If successful, that research could lead to a better understanding of diseases and improved drug discovery and genome mapping approaches, among other potential benefits.

Image Caption: Researchers at Stanford University, funded by DARPA’s Simplifying Complexity in Scientific Discovery (SIMPLEX) program, have created a mathematical framework that automatically identifies and prioritizes the patterns that are fundamental to explaining network structure and function. As part of their research, the team analyzed the U.S. air traffic system (A) using their motif-clustering framework, which ranked airports based on network patterns, or motifs (B)—specifically, how often each airport matched the pattern of a hub. The SIMPLEX algorithms automatically detected the eight largest hubs, demonstrating that the motif-clustering representation accurately captured the hub-and-spoke design of the system (C). Click on image below for high-resolution image.