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

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

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 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.