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.