  We study the problem of online network change point detection. In this
setting, a collection of independent Bernoulli networks is collected
sequentially, and the underlying distributions change when a change point
occurs. The goal is to detect the change point as quickly as possible, if it
exists, subject to a constraint on the number or probability of false alarms.
In this paper, on the detection delay, we establish a minimax lower bound and
two upper bounds based on NP-hard algorithms and polynomial-time algorithms,
i.e., \[ \mbox{detection delay} \begin{cases} \gtrsim \log(1/\alpha)
\frac{\max\{r^2/n, \, 1\}}{\kappa_0^2 n \rho},\\ \lesssim \log(\Delta/\alpha)
\frac{\max\{r^2/n, \, \log(r)\}}{\kappa_0^2 n \rho}, & \mbox{with NP-hard
algorithms},\\ \lesssim \log(\Delta/\alpha) \frac{r}{\kappa_0^2 n \rho}, &
\mbox{with polynomial-time algorithms}, \end{cases} \] where $\kappa_0, n,
\rho, r$ and $\alpha$ are the normalised jump size, network size, entrywise
sparsity, rank sparsity and the overall Type-I error upper bound. All the model
parameters are allowed to vary as $\Delta$, the location of the change point,
diverges. The polynomial-time algorithms are novel procedures that we propose
in this paper, designed for quick detection under two different forms of Type-I
error control. The first is based on controlling the overall probability of a
false alarm when there are no change points, and the second is based on
specifying a lower bound on the expected time of the first false alarm.
Extensive experiments show that, under different scenarios and the
aforementioned forms of Type-I error control, our proposed approaches
outperform state-of-the-art methods.
