CAREER: Scalable Software Infrastructure for Analyzing Complex Networks

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.