CAREER: Quick Detection for Streaming Data Over Dynamic Networks

在S的世界里，通过网络传输数据已经变得无处不在。一个基本问题是如何尽可能快地从网络流数据中检测变化点(在时间和空间上)。这源于广泛的应用，包括地球物理勘探、社会网络监控、电网监控、智能城市的多传感器系统以及网络安全。目前，关于如何对这些数据建模，如何通过严格的理论框架设计算法，如何在线高效地实现算法，以及在控制错误警报的情况下检测变化的速度，我们知道的还很少。拟议的研究将解决这些基本的理论和算法问题。这些努力不仅将带来新的技术进步，还将有助于相关领域更广泛的跨学科受众。该项目的主要研究目标是开发一个模型和算法框架，为网络上的顺序变点检测提供理论上的性能保证。这就弥合了统计方法和计算方法之间的根本差距。在建模方面，提出的工作旨在捕获网络流数据的复杂依赖关系，并利用网络环境中变化的结构。在算法设计方面，目标包括高效的在线实现、对高维的可伸缩性以及对数据动态的适应性。在理论上，目标是建立最优性，并描述虚警和检测延迟之间的基本性能权衡。拟议的研究将建立在对复杂网络数据(如网络点过程和关联网络)建模的最新进展、序贯优化、草图绘制、社区检测和子空间跟踪等算法发展以及尾部概率和极值理论研究的理论进展的基础上。

Streaming data over networks have become ubiquitous in today?s world. A fundamental question is how to detect change-points (over time and space) from network streaming data as quickly as possible. This arises from a wide range of applications including geophysical exploration, social network surveillance, power network monitoring, multi-sensor systems for smart cities, as well as cyber security. Currently, not much is known about how to model these data, how to design an algorithm through a rigorous theoretical framework, how to implement algorithms efficiently online, and how fast we can detect the change with false alarms under control. The proposed research will address these fundamental theoretical and algorithmic questions. The efforts will lead not only to novel technological advances but also help with a much wider interdisciplinary audience in related fields. The overarching research objective of this project is to develop a modeling and algorithmic framework with theoretical performance guarantees for sequential change-point detection over networks. This bridges the fundamental gap between the statistical and computational approaches. Regarding modeling, the proposed work aims to capture complex dependence of network streaming data and exploit the structure of changes in the network setting. Regarding algorithm design, the goals include efficient online implementation, scalability to high dimensionality, and adaptiveness to data dynamics. Regarding theory, the goals are to establish optimality and to characterize the fundamental performance tradeoff between false alarms and detection delay. The proposed research will build on recent progress in modeling complex network data such as network point processes and correlation networks, algorithmic development such as sequential optimization, sketching, community detection, and subspace tracking, as well as theoretical advances in studying tail probabilities and extremal value theory.