When a species disappears from a region, the rest of the ecosystem may flourish or collapse, depending on the role that species played. When a storm rolls across the coast, the power grid might reconfigure itself quickly or leave cities dark for days. A snowstorm might mean business as usual in a hardy city and a severe food shortage in another, depending on the distribution strategies of residents.
Each of these systems is a kind of network, with thousands of members and relationships linking them. Understanding how networks behave is key to ensuring their functioning.
With current network theory, scientists can predict a few simple trends, such as which web pages are likely to get more hits over time. Mostly, current models “flatten” the system to a list of points (nodes) and connections between them (edges). But the features that bestow a network’s true cohesion and character – such as the nuanced predator-prey dynamics in an ecosystem, hierarchies in a social community, or critical hubs in a distribution system – have eluded quantification.
A new four-year, $2.9 million grant from the Defense Advanced Research Projects Agency is supporting SFI research that will, the researchers hope, propel their understanding of networks to the next level.
“If we want to have a power grid that can handle fluctuations in solar and wind power, or know what will happen to the marine food web as the ocean acidifies due to climate change, or see how ideas spread in a social network, we need to understand networks and their dynamics,” says SFI Professor Cris Moore, principal investigator for the project.
Nodes and links in real networks are cloaked in details, he says. In an online community, for example, age, ethnicity, language, and location all can influence a person’s position and behaviors. In a power grid, each link has a capacity and a cost. But how much do we really need to know about nodes and links to understand their roles in the system? More broadly, how much do we need to know about a system’s structure to understand its behavior?
“We’re at a very early stage of understanding how structure is related to dynamics,” Moore says. The project aims to model the immense variety of network structures and related information, devise methods to fit models to data that cover the intricacy of their patterns, and proffer algorithms that can generalize from patchy information and fill in missing information in massive, complex networks.
SFI is the lead institution for the grant, issued by DARPA’s Graph-theoretic Research in Algorithms and the Phenomenology of Social Networks program and the Air Force Office of Scientific Research.
Moore joins SFI External Professors Aaron Clauset, a computer scientist at the University of Colorado at Boulder, and Mark Newman, a statistical physicist at the University of Michigan, in approaching the problem using Bayesian inference and machine-learning algorithms. Such algorithms – which refine themselves in response to the results they generate – can be designed to analyze a network and figure out how its
communities are organized.
Ultimately, the team wants to design algorithms that will analyze a network based on sufficient but incomplete data, make intelligent guesses about gaps in knowledge, indicate which links will form in the future, and note quirks or unusual behaviors in functioning networks.
They have already made progress. In a recent paper, Moore and University of New Mexico computer science grad students Yaojia Zhu and Xiaoran Yan, along with machine-learning expert Lise Getoor of the University of Maryland, developed a model for categorizing a massive set of research papers. Using both the content of the papers and the links (citations) between them, their algorithm outperforms existing methods – and can run on a laptop.
In addition, Moore, Clauset, and Clauset’s student Abigail Jacobs are working with SFI Professor and Chair of the Faculty Jennifer Dunne on predicting parasitic links in food webs. And Newman and his student Brian Ball have developed a new model of social networks that takes social status into account.