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: http://science.sciencemag.org/content/353/6295/163. 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.
Media with inquiries should contact DARPA Public Affairs at firstname.lastname@example.org
Associated images posted on www.darpa.mil and video posted at www.youtube.com/darpatv may be reused according to the terms of the DARPA User Agreement, available here: http://go.usa.gov/cuTXR..
You are now leaving the DARPA.mil website that is under the control and
management of DARPA. The appearance of hyperlinks does not constitute
endorsement by DARPA of non-U.S. Government sites or the information,
products, or services contained therein. Although DARPA may or may not
use these sites as additional distribution channels for Department of
Defense information, it does not exercise editorial control over all of
the information that you may find at these locations. Such links are
provided consistent with the stated purpose of this website.
After reading this message, click to continue