PI: Sajal K. Das

 The goal of this three-year project, Sparsification-based Approach for Analyzing Network Dynamics (SANDY), is to develop a suite of scalable parallel algorithms for updating dynamic networks for different problems that can be executed on a wide range of HPC platforms. Dynamic network analysis will enable researchers to study the evolution of complex systems in diverse disciplines, such as bioinformatics, social sciences, and epidemiology. The SANDY project is expected to initiate a new direction of research in developing parallel dynamic network algorithms that will benefit multiple analysis objectives (e.g., motif finding and network alignment) and application domains (e.g., epidemiology, health care). Research findings will be integrated into courses on network analysis, parallel algorithms, and bioinformatics offered at the three collaborating institutions. The PIs will collaborate with high schools to deliver talks on network theory, and encourage women and minority students to pursue IT-related careers. 

To develop efficient and scalable parallel algorithms, the PIs propose to use an elegant technique, called graph sparsification that expresses graph algorithms in a reduction-like fashion. The formal steps to parallelization, as guided by the graph sparsification framework, provide a template for creating provably correct parallel algorithms for dynamic networks. The proposed algorithms will address the dual needs of portability and performance optimization. The framework will further provide a mechanism for combining high level (e.g., static and dynamic graph partitioning) and low level (e.g., dataflow algorithms) tuning strategies to ensure high performance and scalability for various parallel architectures by considering such factors as scalability, time, memory, and energy efficiency.