Science Magazine Features Prof. Gleich's Research

07-08-2016

Writer(s): Staff Reports

All fields and disciplines in science are now “drowning in data” to use what is a current cliché and everyone is desperate for new ways to organize and understand this information.  Assistant Professor David Gleich, along with co-authors Austin R. Benson and Jure Leskovec of Stanford, have proposed an entirely new and powerful way of organizing networks of data in an article in Science magazine. 

Networks are a standard and intuitive representation of data throughout the sciences.  They consist of objects and their relationships. Facebook is one of the most widely known networks, which consists of people and their friendships. Another example is the airport network, which consists of flights between airports.  “In science, biologists routinely create networks to study the processes inside our bodies and cells. Neuroscientists also use networks to study the interactions in our brains,” Gleich said.

The dominant strategy so far has been to study networks in terms of their individual nodes and edges. Gleich and his colleagues instead study the organization of networks in terms of small patterns, called networks motifs.

“Our approach, uses multiple nodes and edges for our basic analytic tool,” says Austin Benson, a graduate student in computational mathematics at Stanford University. “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.”

“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,” says Leskovec, an assistant professor at Stanford University. He notes that this development could streamline research in many fields.

Gleich and his collaborators said their new technique has fundamental advantages over previous work on a problem that is generally referred to as community detection, graph partitioning, or network clustering.  

“More and more, large, complicated data sets are presented as networks,” Benson says. “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. 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.”

One of the key features of their method is that it is able to capture the complexity of modern network data that includes directed edges, like one-way roads, and various behaviors that exist on an edge, such as if one gene is activated, then another gene is repressed. “Because we use a new way of representing the network for analysis, our method is easily able to work with these directed and signed networks, whereas most existing methods used representations that didn’t precisely preserve the meaning of these features,” Gleich continued.

One of the challenges the team faced was keeping the final method they developed easy to use. “This is a powerful new idea. Towards that end, we built a project website where anyone can reproduce the figures from our paper on their own system. We hope this will enable them to use our new techniques on their own data to quickly find new insights in their own domains.”  

For more information, please read their report in Science: Austin R. Benson, David F. Gleich, Jure Leskovec. Higher-order organization of complex networks. Science, 2016 http://science.sciencemag.org/content/353/6295/163 and the associated Perspective piece by Nataša Pržulj and Noël Malod-Dognin, Network analytics in the age of big data:  http://dx.doi.org/10.1126/science.aah3449.

Their code and data are also available at http://snap.stanford.edu/higher-order/.

The Stanford News service has also written a complementary article about their work at http://news.stanford.edu/press-releases/2016/07/08/stanford-led-effcontrol-networks/.

More coverage available at: http://phys.org/news/2016-07-mathematical-framework-network-relationships.html.