U.S. university researchers devise new way to analyze networks

Researchers at two U.S. universities have devised a new way to describe networks, hopefully helping with analyzing brain structure, cell metabolism, social media and transportation systems.

Jure Leskovec, associate professor of computer science at Stanford University, has worked with Austin Benson, a doctoral student in computational mathematics at the school in northern California, and David Gleich, an assistant professor of computer science at Purdue University, to take a modular approach to network description by assembling key network elements into "motifs."

They envision the whole network as a series of motifs, or modules comprised of smaller network chunks.

"In the past few years, there has been progress in describing networks through 'nodes' and 'edges,' " Leskovec, senior author of a recent journal Science article, was quoted as saying in a news release from Stanford. "For example, say you' re looking at an air transportation system, and there' s a flight between two cities. The cities would be nodes, and the line between them would be an edge."

However, said Leskovec, the node-and-edge approach is like looking at a wall one brick at a time, and focusing on these smaller details may impede efforts to see the bigger picture.

Instead, the modular approach looks at small sections of bricks that make it much more efficient to perceive the overall structure of the wall. "Our approach uses multiple nodes and edges for our basic analytic tool," said Benson. "Instead of two cities and a flight line for an air transportation network, we'll incorporate another city or cities, and additional flight lines. That allows us to create 'motifs' - small networks that are essentially modules that can be used to predict and control larger networks."

Building on 40 years of research in mathematics and theoretical computer science, the researchers said, an analysis based on motifs rather than the network bricks has benefits beyond the speed of analytical insight. "By incorporating more data into your basic building block, you end up with a complex network description that is far richer than any that would result from a node-and-edge approach," Leskovec said, noting that this development could streamline research in many fields, including food webs that characterize natural marine and terrestrial environments.

"Food webs are basically energy transport systems," he said. "They're networks of energy flowing from smaller animals to larger ones in a given ecosystem. So, if we understand, say, a marine food web in detail, if there's a lot of granularity in our model, we can understand the potential adverse impacts of various developments or actions. We could see how climate change or pollution might affect plankton and smaller fish and, ultimately, salmon and other food fish."

"This is such a powerful new idea that we worked hard to simplify these complexities," Gleich said, acknowledging that the researchers strove to create an approach that would be easy for others to use.

"More and more, large, complicated data sets are presented as networks. But it's virtually impossible to look at any one of these sets as a whole because they' re simply too big," Benson said. "Our method allows you to break data into components that can be understood, and then used to describe and understand the bigger, complex networks to which they belong." Endit