We study the problem of change point localization in dynamic networks models. We assume that we observe a sequence of independent adjacency matrices of the same size, each corresponding to a realization of an unknown inhomogeneous Bernoulli model. The underlying distribution of the adjacency matrices are piecewise constant, and may change over a subset of the time points, called change points. We are concerned with recovering the unknown number and positions of the change points. In our model setting we allow for all the model parameters to change with the total number of time points, including the network size, the minimal spacing between consecutive change points, the magnitude of the smallest change and the degree of sparsity of the networks. We first identify a region of impossibility in the space of the model parameters such that no change point estimator is provably consistent if the data are generated according to parameters falling in that region. We propose a computationally-simple algorithm for network change point localization, called Network Binary Segmentation, that relies on weighted averages of the adjacency matrices. We show that Network Binary Segmentation is consistent over a range of the model parameters that nearly cover the complement of the impossibility region, thus demonstrating the existence of a phase transition for the problem at hand. Next, we devise a more sophisticated algorithm based on singular value thresholding, called Local Refinement, that delivers more accurate estimates of the change point locations. Under appropriate conditions, Local Refinement guarantees a minimax optimal rate for network change point localization while remaining computationally feasible.
翻译:我们研究动态网络模型中的改变点本地化问题。 我们假设, 我们观察的是一组大小相同的独立相邻矩阵序列, 每个大小都对应一个未知的不相容伯努利模型的实现。 相邻矩阵的基本分布是片状不变的, 可能会在特定时间点中发生变化, 称为变化点。 我们关心的是恢复变化点的未知数量和位置。 在模型设置中, 我们允许所有模型参数随着时间点总数的变化而变化, 包括网络规模、 连续变化点之间的最小间距、 最小变化的规模和网络的宽度。 我们首先确定一个在模型参数空间中不可能的区域, 如果数据是根据该区域下降的参数生成, 则没有改变点估计值, 并且可能改变。 我们提出了网络变位点的计算简单算法算法, 即网络变异点的加权平均数, 连续变化点之间的间隔距离, 最小变化幅度的最小值范围是网络的精确值, 从而显示最精确的本地变点的精确值 。