  In a sequence of multivariate observations or non-Euclidean data objects,
such as networks, local dependence is common and could lead to false
change-point discoveries. We propose a new way of permutation -- circular block
permutation with a random starting point -- to address this problem. This
permutation scheme is studied on a non-parametric change-point detection
framework based on a similarity graph constructed on the observations, leading
to a general framework for change-point detection for data with local
dependency. Simulation studies show that this new framework retains the same
level of power when there is no local dependency, while it controls type I
error correctly for sequences with and without local dependency. We also derive
an analytic p-value approximation under this new framework. The approximation
works well for sequences with length in hundreds and above, making this
approach fast-applicable for long data sequences.
