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.

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