SPX: Collaborative Research: SANDY: Sparsification-based Approach for Analyzing Network Dynamics

这个为期三年的项目-基于稀疏化的网络动力学分析方法(SADY)的目标是开发一套可扩展的并行算法，用于针对不同的问题更新动态网络，这些算法可以在广泛的HPC平台上执行。动态网络分析将使研究人员能够研究不同学科的复杂系统的进化，如生物信息学、社会科学和流行病学。预计Sandy项目将在开发并行动态网络算法方面开创一个新的研究方向，这些算法将有利于多个分析目标(例如，基元发现和网络比对)和应用领域(例如，流行病学、医疗保健)。研究成果将被整合到三个合作机构提供的网络分析、并行算法和生物信息学课程中。PI将与高中合作讲授网络理论，并鼓励女性和少数族裔学生从事与IT相关的职业。为了开发高效和可扩展的并行算法，PI建议使用一种称为图稀疏的优雅技术，以类似约简的方式表示图算法。在图稀疏框架的指导下，并行化的正式步骤为为动态网络创建可证明正确的并行算法提供了模板。提出的算法将解决可移植性和性能优化的双重需求。该框架还将提供用于组合高级(例如，静态和动态图划分)和低级(例如，数据流算法)调整策略的机制，以通过考虑诸如可伸缩性、时间、存储器和能量效率等因素来确保各种并行体系结构的高性能和可伸缩性。

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.