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

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

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.