Collaborative Research: ATD: Theory and Algorithms for Discrete Curvatures on Network Data from Human Mobility and Monitoring

合作研究：ATD：人体移动和监测网络数据离散曲率的理论和算法

• 批准号: 1737876
• 负责人: Feng Luo
• 金额: $ 15万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-08-15 至 2020-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1737876&HistoricalAwards=false
• 关键词: Collaborative; Research; ATD; Theory; Algorithms

New developments in technologies of embedded systems, sensors, and wireless communications provide great potential to improve the safety and security of the physical and social environment we live in. These technologies can help identify and mitigate unfortunate accidents, emergency events, and malicious attacks. This project seeks to develop mathematical tools and algorithms based on discrete curvatures for the purpose of understanding and detecting community structures and anomalies in networks that can be of crucial value in many applications. The project considers high level mobility patterns, community structures, and anomalies as well as finer details such as who is where. The mathematical tools to be developed will be useful in other networks (for example, protein-protein interactions in biological networks). This project will investigate mathematical problems arising the analysis of real-time spatial and temporal human mobility data. The focus will be on the community detection problem on graphs by using discrete Ricci curvatures and discrete curvature flows on graphs. The problem is to extract stable groups in human mobility patterns, which will serve as the traffic norm for detecting abnormal patterns that can be tied to criminal or terroristic events. To detect these stable groups, or communities, the main observation is that community structures in a network resemble well known geometric phenomena such as thick-thin decompositions in Riemannian geometry. Inspired by Riemannian geometry and the success of Hamilton-Perelman's Ricci flow program, this work investigates how to use discrete curvatures and discrete curvature flows to detect community structure in a network. Preliminary investigations show that the proposed method has great potential and can detect communities with high accuracy. This potential prompts the PIs to examine computationally feasible definitions of discrete Ricci curvatures on weighted networks. The important work of Ollivier on discrete Ricci curvature is the starting point of this investigation. The drawback of Ollivier's curvature is that it is computationally expensive -- almost impossible to compute the proposed discrete curvature flow on large networks containing more than a million nodes. As such, the main task in this work is to find computationally feasible Ricci curvatures where the discrete curvature flow can be computed in real time for large networks. The affirmative resolution of this work will be useful in pure mathematical research and computer science. The work will also develop software for practical use.

嵌入式系统、传感器和无线通信技术的新发展为改善我们生活的物理和社会环境的安全性提供了巨大的潜力。 这些技术可以帮助识别和减轻不幸的事故、紧急事件和恶意攻击。该项目旨在开发基于离散曲率的数学工具和算法，以理解和检测网络中的社区结构和异常，这些结构和异常在许多应用中具有至关重要的价值。该项目考虑了高级别的移动模式，社区结构和异常以及更精细的细节，如谁在哪里。 待开发的数学工具将在其他网络中（例如，生物网络中的蛋白质-蛋白质相互作用）有用。该项目将研究分析实时空间和时间人类流动数据所产生的数学问题。 重点将是社区检测问题的图上使用离散Ricci曲率和离散曲率流图。 问题是提取稳定的人群流动模式，这将作为交通规范检测异常模式，可以绑定到犯罪或恐怖事件。为了检测这些稳定的群体或社区，主要的观察是网络中的社区结构类似于众所周知的几何现象，例如黎曼几何中的厚-薄分解。受黎曼几何和Hamilton-Perelman的Ricci流程序的启发，本文研究了如何使用离散曲率和离散曲率流来检测网络中的社区结构。 初步调查表明，该方法具有很大的潜力，可以检测社区与高精度。 这种潜力促使PI检查加权网络上离散Ricci曲率的计算可行的定义。重要的工作奥利维尔离散里奇曲率是出发点，这项调查。 Ollivier曲率的缺点是计算成本很高--几乎不可能在包含超过一百万个节点的大型网络上计算所提出的离散曲率流。 因此，在这项工作中的主要任务是找到计算上可行的Ricci曲率的离散曲率流可以在真实的时间计算大型网络。这一结论在纯数学研究和计算机科学中具有一定的应用价值。 这项工作还将开发实用软件。

项目成果

An effective Lie–Kolchin Theorem for quasi-unipotent matrices

拟单能矩阵的有效李科尔钦定理

• DOI: 10.1016/j.laa.2019.07.023
• 发表时间: 2019
• 期刊: Linear Algebra and its Applications
• 影响因子: 1.1
• 作者: Koberda, Thomas;Luo, Feng;Sun, Hongbin
• 通讯作者: Sun, Hongbin

A discrete uniformization theorem for polyhedral surfaces II

• DOI: 10.4310/jdg/1531188190
• 发表时间: 2014-01
• 期刊: Journal of Differential Geometry
• 影响因子: 2.5
• 作者: X. Gu;Ren Guo;F. Luo;Jian Sun;Tianqi Wu