Salapaka, Beck simplify dynamic graphs for more meaningful data analysis

 

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, Srinivasa Salapaka, an associate professor in MechSE, along with Carolyn Beck, an associate professor in the Department of Industrial and Enterprise Systems Engineering, are developing algorithms to simplify and facilitate analysis of these large networks. Salapaka and Beck are also faculty affiliates in the Coordinated Science Lab at Illinois.

 

“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, the two 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.

 

Salapaka joined the MechSE department in 2004 as an assistant professor. He earned an MS and PhD in mechanical engineering from the University of California, Santa Barbara, in 1997 and 2002. His research focuses on the area of controls and dynamics, with an emphasis on instrumentation and methodologies for use in nano-biotechnology; classification, clustering, and aggregation of large data sets; and application of modern systems techniques for control of power-grid/power electronics technologies.