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

嵌入式系统、传感器和无线通信技术的新发展为改善我们生活的物理和社会环境的安全和保障提供了巨大的潜力。这些技术可以帮助识别和减少不幸的事故、紧急事件和恶意攻击。该项目旨在开发基于离散曲率的数学工具和算法，以了解和检测网络中的社区结构和异常，这些结构和异常在许多应用中可能具有关键价值。该项目考虑了高级流动模式、社区结构和异常情况，以及更详细的细节，如谁在哪里。将要开发的数学工具将在其他网络中有用(例如，生物网络中的蛋白质-蛋白质相互作用)。该项目将研究在分析实时空间和时间人员流动数据时产生的数学问题。利用图上的离散Ricci曲率和离散曲率流，重点研究了图上的社区发现问题。问题是从人类流动模式中提取稳定的群体，这将作为检测可能与犯罪或恐怖事件有关的异常模式的流量规范。为了检测这些稳定的群体或群落，主要观察到网络中的群落结构类似于众所周知的几何现象，如黎曼几何中的粗-薄分解。受Riemannian几何和Hamilton-Perelman的Ricci流程序的成功启发，本文研究了如何使用离散曲率和离散曲率流来检测网络中的社区结构。初步研究表明，该方法具有很大的潜力，能够较高的准确率地检测出社区。这种可能性促使PI检查加权网络上离散Ricci曲率在计算上的可行定义。Olivier关于离散Ricci曲率的重要工作是本文研究的起点。奥利维尔曲率的缺点是计算昂贵--几乎不可能在包含100多万个节点的大型网络上计算所提出的离散曲率流。因此，这项工作的主要任务是找到计算上可行的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.