Graphic by Harvepino, Shutterstock: Researchers from Stanford have developed a new analytical tool that makes it easier to understand and manage complex networks.
Stanford News - July 8th, 2016 - by Glen Martin
There is a great deal of truth to the old saw that everything is connected. Networks, in fact, are a highly useful means for describing almost anything, including brain structure, cell metabolism, social media and transportation systems.
Accurately determining the configurations of large networks makes them easier to control, maximizing technological benefits while avoiding blunders. But so far, the tools for describing large networks have been insufficient relative to the complexity of the systems they seek to manage.
In an article for Science, two Stanford researchers in collaboration with a Stanford alumnus now at Purdue have revealed a new and more useful approach for describing and, ultimately, managing complex networks. Their method simplifies what would otherwise be a daunting undertaking by envisioning the whole as a series of “motifs” – modules comprised of smaller network chunks.
“In the past few years, there has been progress in describing networks through ‘nodes’ and ‘edges,’” said Jure Leskovec, associate professor of computer science and senior author of the Science article. “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.”
The bigger picture
The node-and-edge approach can be used to study large networks, said Leskovec, but the process is like looking at a wall one brick at a time. At the same time, focusing on these smaller details may impede efforts to see the bigger picture.
So, instead of going brick by brick, Leskovec and his co-authors, Austin Benson, a Stanford doctoral student in computational mathematics, and David Gleich, an assistant professor of computer science at Purdue, are taking a modular approach to network description. Their approach assembles key network elements into motifs or, to continue the metaphor, they look 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 [of the whole] that can be used to predict and control larger networks.”
‘Networks of energy’
Basing an analysis on motifs rather than the simpler network bricks of earlier methodologies has benefits beyond the speed of analytical insight, the researchers contend.
“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.
He noted 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,” Leskovec 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.”
Social media
Benson said the motif approach also allows greater understanding of social networks. In Facebook, he observes, people serve as nodes and their “friendships” function as edges, or connections. Typically, descriptions of Facebook networks have been predicated on friendships between two people.
“But adding even one person, creating a triangle of friends instead of an edge anchored by two nodes, results in a much more powerful analytic tool,” he said. “It allows you a much closer look at ‘micropatterned’ relationships and, ultimately, a far better understanding of the larger network and a clearer idea of what’s going on with the participants.”
Simple logic dictates that such “motifs” should provide both quicker analyses of complex networks and better results than previous methods, but translating the obvious into functional algorithms can be a very heavy lift, Leskovec said.
“Going from nodes-and-edges to small network components turned out to be quite difficult,” he said. “We did it, but it certainly wasn’t easy.”
Gleich says this new motif approach builds on 40 years of research in mathematics and theoretical computer science; the researchers strove to create an approach that would be easy for others to use.
“This is such a powerful new idea that we worked hard to simplify these complexities” he said.
Ultimately, this motif methodology could find broad applications across many scientific fields because technical information increasingly is expressed in network terms.
Benson said, “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. You have to be able to tear them into pieces to understand the whole. And not only that, how you look at the pieces is very important.”
He added, “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.”
Their paper in Science is titled “Higher-order organization of complex networks.”
