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

III：小型：协作研究：通过全局曲率进行网络分析和异常检测

• 批准号: 1814931
• 负责人: Bhaskar DasGupta
• 金额: $ 35万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-08-15 至 2022-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814931&HistoricalAwards=false
• 关键词: III; Small; Collaborative; Research; Network

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.

在更高维度中的几何形状和拓扑空间的曲率是对较高维度的自然而有力的概括，并且在物理，数学和许多其他领域中起着基本作用。 在这项合作跨学科的建议中，涉及伊利诺伊大学芝加哥大学和宾夕法尼亚州立大学的一名调查员，研究人员将使用强大的高维曲率分析方法来提供系统和计算高效的方法的基础，以查找关键组成部分，测量冗余和检测生物学和社交网络。对此有迫切的需求，因为关键组件的识别对于对网络的分析至关重要，基于曲率的分析方法提供了一种使用系统和严格的理论框架来满足这一需求的原则方法，以实现清晰的理解。拟议的研究还将利用研究人员先前开发的新型组合工具的进一步开发，除了开发新的算法和近似性技术。在本项目过程中开发的算法将实施以验证模拟和真实数据，并将为相关研究社区提供开源软件。除了在网络分析中产生重大影响外，拟议的研究还将对计算生物学，神经科学和社交网络分析的许多其他研究领域产生强大的影响。 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基于测量学和高阶连接性的特性以及基于基于几何络合物识别网络的几何曲率以及使用RICCI类型曲率的组合化的几何曲率。这些曲率度量取决于非平凡的全局特性，例如地球学的分布和节点之间的高阶相关性，与给定网络的分布，而不是许多其他本质上的局部措施。 研究人员将使用这些概念来识别网络的非平凡关键组成部分，其去除会影响网络拓扑或动态的变化。 研究人员将在数学上提出精确的计算问题，研究其特性，使用新颖的算法工具来设计有效的算法，并实施所得的算法以测试其准确性和效率。 两位研究者的互补背景，即计算机科学和计算生物学（Dasgupta）（Dasgupta）以及对生物和社交网络（Albert）（Albert）的建模和分析的组合优化，将使两个研究人员成为该提案中跨学科应用的理想团队，这些奖项通过评估NSF的法规及其范围的范围，这表明了NSF的法规及其在范围内的支持。 标准。

项目成果

Why Did the Shape of Your Network Change? (On Detecting Network Anomalies via Non-local Curvatures)

• DOI: 10.1007/s00453-019-00665-7
• 发表时间: 2020-01-22
• 期刊: ALGORITHMICA
• 影响因子: 1.1
• 作者: DasGupta, Bhaskar;Janardhanan, Mano Vikash;Yahyanejad, Farzane
• 通讯作者: Yahyanejad, Farzane

A survey of some tensor analysis techniques for biological systems

生物系统一些张量分析技术综述

• DOI: 10.1007/s40484-019-0186-5
• 发表时间: 2019
• 期刊: Quantitative Biology
• 影响因子: 3.1
• 作者: Yahyanejad, Farzane;Albert, Réka;DasGupta, Bhaskar
• 通讯作者: DasGupta, Bhaskar