Mathematical framework offers a more detailed understanding of network relationships

July 8, 2016 by Bob Yirka report
social network
Social network diagram. Credit: Daniel Tenerife/Wikipedia

(Phys.org)—A trio of math and computer scientists has developed a means for developing generalized frameworks that allow for clustering networks based on higher-order connectivity patterns. In their paper published in the journal Science, Austin Benson and Jure Leskovec with Stanford University and David Gleich with Purdue University outline their framework ideas and offer real life examples of ways their techniques can be applied to help understand complex networks in simpler ways. Nataša Pržulj and Noël Malod-Dognin with University College London offer an analysis of the work done by the trio in a Perspectives piece in the same journal issue.

As the authors note, it is not difficult to make out patterns in very small networks, a person trying to do so need only watch the system at work for a period of time. It is when networks become bigger and more complex that they become unwieldy. Even in such cases, however, low-order patterns are often still easy to discern—counting nodes or edges for example, offers some degree of network size, though doing so tells you very little about what the network does and how—that is where high-order organizational principles come into play. Unfortunately attempts to create a means for providing more information or detail about such systems has to date, not met with much success. In this new effort, the researchers describe a framework they have developed that offers some of the pattern recognition seen in smaller networks, with more .

They start, Pržulj and Malod-Dognin note, with one of the more common higher-order structures known as small network subgraphs, which they refer to as network motifs—those that are statistically significant can be used as building blocks for the building of a mathematical framework, which is of course what the researchers have done. Relationship identification among the motifs was done by applying clustering algorithms. The result is a framework that highlights and/or identifies which of the motifs are the most critical when a network is in operation.

The trio tested their technique by using it to analyze part of the neuronal of a roundworm, and report that it revealed the particular cluster of 20 neurons responsible for performing actions such as standing and wiggling its head. They also gained insights into air traffic patterns by using it to perform an analysis of airports in the U.S. and Canada. They suggest such frameworks may be used in a wide variety of applications.

Explore further: Unraveling biological networks

More information: A. R. Benson et al. Higher-order organization of complex networks, Science (2016). DOI: 10.1126/science.aad9029

Abstract
Networks are a fundamental tool for understanding and modeling complex systems in physics, biology, neuroscience, engineering, and social science. Many networks are known to exhibit rich, lower-order connectivity patterns that can be captured at the level of individual nodes and edges. However, higher-order organization of complex networks—at the level of small network subgraphs—remains largely unknown. Here, we develop a generalized framework for clustering networks on the basis of higher-order connectivity patterns. This framework provides mathematical guarantees on the optimality of obtained clusters and scales to networks with billions of edges. The framework reveals higher-order organization in a number of networks, including information propagation units in neuronal networks and hub structure in transportation networks. Results show that networks exhibit rich higher-order organizational structures that are exposed by clustering based on higher-order connectivity patterns.

Related Stories

Unraveling biological networks

March 5, 2012

A new approach to disentangling the complexities of biological networks, such as the way in which proteins interact in our body's cells has been developed by researchers in China. The team's algorithm could allow biologists ...

New framework uses patterns to predict terrorist behavior

June 28, 2016

Government agencies are having difficulty tracking potential terrorist attacks, since terrorists have developed new ways to communicate besides social media. A new framework developed by researchers at Binghamton University, ...

How cooperation emerges in competing populations

July 7, 2016

Social behaviour like reaching a consensus is a matter of cooperation. However, individuals in populations often spontaneously compete and only cooperate under certain conditions. These problems are so ubiquitous that physicists ...

Getting inside the control mechanisms of complex systems

May 13, 2011

Northeastern University researchers are offering a fascinating glimpse into how greater control of complex systems, such as cellular networks and social media, can be achieved by merging the tools of network science and control ...

Recommended for you

Metacognition training boosts gen chem exam scores

October 20, 2017

It's a lesson in scholastic humility: You waltz into an exam, confident that you've got a good enough grip on the class material to swing an 80 percent or so, maybe a 90 if some of the questions go your way.

Scientists see order in complex patterns of river deltas

October 19, 2017

River deltas, with their intricate networks of waterways, coastal barrier islands, wetlands and estuaries, often appear to have been formed by random processes, but scientists at the University of California, Irvine and other ...

Six degrees of separation: Why it is a small world after all

October 19, 2017

It's a small world after all - and now science has explained why. A study conducted by the University of Leicester and KU Leuven, Belgium, examined how small worlds emerge spontaneously in all kinds of networks, including ...

Ancient DNA offers new view on saber-toothed cats' past

October 19, 2017

Researchers who've analyzed the complete mitochondrial genomes from ancient samples representing two species of saber-toothed cats have a new take on the animals' history over the last 50,000 years. The data suggest that ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.