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

点击翻译按钮获取中文摘要

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.