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.