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

高维几何形状和拓扑空间的曲率是平面到高维的自然而有力的推广，在物理、数学和许多其他领域发挥着重要作用。在这项跨学科合作提案中，来自芝加哥伊利诺伊大学和宾夕法尼亚州立大学的研究人员将使用强大的高维曲率分析方法，为寻找关键组件、测量冗余和检测生物和社会网络中的异常提供系统和计算效率方法的基础。这是迫切需要的，因为关键组件的识别对网络分析至关重要，而基于曲率的分析方法提供了一种原则性的方法，使用系统和严格的理论框架来满足这一需求，以实现清晰的理解。除了开发新的算法和近似技术外，拟议的研究还将利用先前研究人员开发的新型组合工具的进一步开发。在此项目中开发的算法将在模拟和真实数据上进行验证，并将为相关研究团体提供开源软件。除了对网络分析产生重大影响外，拟议的研究还将对计算生物学、神经科学和社会网络分析等许多其他研究领域产生重大影响。其他更广泛的影响将包括通过课程和课程编制将研究和教育结合起来，使本科生、少数民族和代表性不足的群体参与，有效传播研究成果，指导本科生和研究生，扩大和社区参与，以及促进有关研究和教育活动的多样性。为了实现本项目的目标，研究者将探索两个曲率概念，即基于测地线和高阶连通性的gromov -双曲曲率，以及基于几何复合体识别网络和使用Ricci型曲率组合化的几何曲率。这些曲率度量依赖于给定网络的非平凡全局属性，如测地线分布和节点之间的高阶相关性，而不是许多其他局部度量。研究人员将使用这些概念来识别网络中重要的关键组件，这些组件的移除会以重要的方式影响网络拓扑或动态的变化。研究人员将制定精确的数学计算问题，研究其性质，使用新颖的算法工具来设计有效的算法，并实施结果算法来测试其准确性和效率。两位研究人员的互补背景，即计算机科学和计算生物学的组合优化（DasGupta）和生物和社会网络的建模和分析（Albert），将使两位研究人员成为本提案中跨学科应用的完美团队。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.