III: Small: Collaborative Research: Network Analysis and Anomaly Detection via Global Curvatures

Curvatures of geometric shapes and topological spaces in higher dimension are natural and powerful generalizations of planes to higher dimensions, and play a fundamental role in physics, mathematics, and many other areas. In this collaborative interdisciplinary proposal involving one investigator each from the University of Illinois at Chicago and the Pennsylvania State University, the investigators will use powerful higher-dimensional curvature analysis methods to provide the foundations of systematic and computationally efficient approaches to find critical components, measure redundancies and detect anomalies in biological and social networks. There is a pressing need for this, as identification of critical components are crucial to the analysis of networks, and curvature-based analysis methods provide a principled way of satisfying this need using a systematic and rigorous theoretical framework to achieve a clear understanding. The proposed research will leverage further development of novel combinatorial tools previously developed by the investigators, in addition to developing new algorithmic and approximability techniques. The algorithms developed in the course of this project will be implemented for validation on simulated and real data and will lead to open-source software for the relevant research communities. In addition to substantial impacts in network analysis, the proposed research will have strong impacts on many other research areas in computational biology, neuroscience, and social network analysis. Other broader impacts will include integration of research and education via course and curriculum development, involvement of undergraduates, minorities and under-represented groups, effective dissemination of research, mentoring of undergraduate and graduate students, outreach and community involvement, and promoting diversity in related research and educational activities. To achieve the goals of this project, the investigators will explore two notions of curvature, namely Gromov-hyperbolic curvature based on the properties of geodesics and higher-order connectivities, and geometric curvatures based on identifying networks with geometric complexes and using combinatorialization of Ricci type curvatures. These curvature measures depend on non-trivial global properties, such as distributions of geodesics and higher-order correlations among nodes, of the given network as opposed to many other measures that are local in nature. The investigators will use these notions to identify non-trivial critical components of the network whose removal affects the change the network topology or dynamics in a significant manner. The investigators will formulate mathematically precise computational problems, study their properties, use novel algorithmic tools to design efficient algorithms, and implement the resulting algorithms to test their accuracy and efficiency. The complementary backgrounds of the two investigators, namely combinatorial optimization in computer science and computational biology (DasGupta) and modelling and analysis of biological and social networks (Albert), will make the two investigators a perfect team for the interdisciplinary applications in this proposal. 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.