Beck, Salapaka work to simplify dynamic graphs

Scientific, engineering, and healthcare-related problems are frequently illustrated using graph-based models, which are often extremely large, complex and difficult to interpret. 

Through a three-year, $300,000 grant from the National Science Foundation, CSL faculty members Carolyn Beck, an associate professor of industrial and enterprise systems engineering, and Srinivasa Salapaka, an associate professor of mechanical science and engineering, are developing algorithms to simplify and facilitate analysis of these large networks.

“Our algorithms create simpler graphs that are quantifiably similar to the larger ones, but that are easier to analyze,” Salapaka said.

For example, in neuroscience, large graphs are used to model causal relationships between different neurons. By applying Beck and Salapaka’s techniques, it is possible to obtain simpler, aggregated graphs that facilitate the identification of functional relationships between different parts of the brain. This research can be applied in a variety of fields, such as analysis of cellular phone calling patterns or social networks, or investigation of the spread of infectious diseases.

“The associated graphs are huge and complex, and you want to find groupings that tell you something about underlying structures,” Beck said.

In the field of clustering and pattern classification, there are many researchers working on graph aggregation; however, Beck and Salapaka’s work stands out by simultaneously incorporating dynamics, communication, and other constraints.

“For example, in a dynamic communication network, the connections may grow stronger or weaker over time,” Salapaka said. “Our method makes it possible to include these variations.”

In addition, Beck and Salapaka have proposed a systematic method that uses quantitative metrics to evaluate how well a simplified graph represents the larger graph.

“Our metrics allow for comparing graphs of different dimensions, thus extending existing graph comparison metrics,” Beck said.

They are working with experts in specific fields, such as neuroscience, to apply their methods to real data and confirm that the results of their algorithms are valuable and readable to the experts who might use them.

While the algorithms are adaptable to different data, each data set is different, and that requires researchers to have some domain-specific knowledge. Beck and Salapaka plan to make their software open source, so researchers in other areas can help build and expand the algorithms to fit many domains.