Change-Point Detection for Dynamic Networks

Résumé

A dynamic network is a sequence of random graphs observed in time. Structural changes occur in dynamic networks quite frequently and their detection is an important question in many situations such as fraud detection or cybersecurity. The time instants of such changes are called change points. I will talk about statistical tests that allow the detection of changes in a sequence of sparse high-dimensional graphs. According to the minimax theory of statistical testing, the test performance is measured by the minimax separation rate. We show that our test based on the Matrix CUSUM statistic is minimax rate-optimal for the inhomogeneous random graph model. We generalize our results to the model of graphons and derive an optimal test for K-step graphons. The results will be illustrated by a real-data example. It is a joint work with Olga Klopp.