CAREER: Scalable Software Infrastructure for Analyzing Complex Networks

实体之间的互动是世界范围内物理、社会和网络物理系统的基础。在这些复杂的网络中，顶点象征实体，边描述实体之间的相互作用。大规模网络在科学和商业应用中非常普遍，例如具有数十亿个顶点和数万亿条边的蛋白质相似网络。随着网络的持续增长，对能够利用大规模网络基础设施来分析跨科学领域的大规模网络的算法和软件的需求越来越大。该项目通过开发由可扩展、可移植和用户友好的图形分析的基本算法组成的软件基础设施来满足这一需求，确保可扩展到数万亿条边、在异类基础设施上的最佳性能以及领域科学家的可访问性。这一软件基础设施直接增强了极端天气预测、新蛋白质发现和工业环境中能源使用预测的重要应用。该项目将这些先进技术的可获得性扩展到不同学术水平的学生。与印第安纳州农村地区高中学生和教师的大学课程和倡议相结合，确保了广泛的教育影响。一个复杂的网络，在数学中被建模为图形，揭示了复杂的拓扑特征，包括动态边、顶点以及静态和动态的混合。由于这种网络的不可预测性和动态性，为每个应用独立开发可扩展的算法和软件在时间、精力和研究资金方面都变得令人望而却步。本项目通过引入通用软件基础设施来应对这些挑战，该软件基础设施专为分析复杂网络并从中学习而量身定做。用户可以利用此基础设施来加速大量基于图形的应用程序。面对图形和计算平台的多样性，该项目采用了灵活的两层框架。该框架将动态图形和机器学习计算无缝地映射到一组简明的稀疏矩阵运算，随后开发了并行算法。这种线性-代数映射提供了从数学算法描述到稀疏矩阵函数的透明路径，确保了多级别的并行性、通信减少和极高的可扩展性。可用性是这项工作中的第二个挑战，通过一套为复杂和动态网络量身定做的新的无监督和有监督的图形算法来解决。将这些创新的图形算法与大规模并行稀疏矩阵运算相结合，产生了一个通用的软件框架，可以分析复杂的时空系统，如流、交通流和能源系统。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Interactions among entities are fundamental to physical, social, and cyber-physical systems worldwide. In these complex networks, vertices symbolize entities, and edges depict their interactions. Large-scale networks are prevalent in scientific and business applications, such as protein similarity networks with billions of vertices and trillions of edges. As networks continue to grow, there is an increasing demand for algorithms and software capable of utilizing large-scale cyberinfrastructure for analyzing massive networks across scientific domains. This project addresses this need by developing a software infrastructure consisting of foundational algorithms for scalable, portable, and user-friendly graph analysis, ensuring scalability to trillions of edges, optimal performance on heterogeneous infrastructures, and accessibility for domain scientists. This software infrastructure directly enhances vital applications in extreme weather prediction, the discovery of novel proteins, and forecasting energy usage in industrial settings. The project extends the accessibility of these advanced technologies to students at various academic levels. Integration with university courses and initiatives for high school students and teachers in rural Indiana ensures widespread educational impact.A complex network, modeled as a graph in mathematics, reveals intricate topological features encompassing dynamic edges, vertices, and a mixture of static and dynamic ones. Due to such networks' unpredictable and dynamic nature, the independent development of scalable algorithms and software for each application has become prohibitively costly in terms of time, effort, and research funding. This project addresses these challenges by introducing a general-purpose software infrastructure tailored to analyze and learn from complex networks. Users can leverage this infrastructure to expedite a multitude of graph-based applications. Confronting the diversity of graphs and computing platforms, the project employs a flexible two-layer framework. This framework seamlessly maps dynamic graph and machine learning computations to a concise set of sparse matrix operations, followed by the development of parallel algorithms. This linear-algebraic mapping offers a transparent pathway from mathematical algorithm descriptions to sparse-matrix functions, ensuring multiple levels of parallelism, communication reduction, and extreme scalability. Usability, the second challenge in this undertaking, is addressed through a comprehensive set of novel unsupervised and supervised graph algorithms tailored for complex and dynamic networks. Integrating these innovative graph algorithms with massively parallel sparse matrix operations results in a versatile software framework that analyzes complex spatiotemporal systems such as streamflow, traffic flow, and energy systems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.