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.


翻译:我们研究动态网络模型中的改变点本地化问题。 我们假设, 我们观察的是一组大小相同的独立相邻矩阵序列, 每个大小都对应一个未知的不相容伯努利模型的实现。 相邻矩阵的基本分布是片状不变的, 可能会在特定时间点中发生变化, 称为变化点。 我们关心的是恢复变化点的未知数量和位置。 在模型设置中, 我们允许所有模型参数随着时间点总数的变化而变化, 包括网络规模、 连续变化点之间的最小间距、 最小变化的规模和网络的宽度。 我们首先确定一个在模型参数空间中不可能的区域, 如果数据是根据该区域下降的参数生成, 则没有改变点估计值, 并且可能改变。 我们提出了网络变位点的计算简单算法算法, 即网络变异点的加权平均数, 连续变化点之间的间隔距离, 最小变化幅度的最小值范围是网络的精确值, 从而显示最精确的本地变点的精确值 。

0
下载
关闭预览

相关内容

Networking:IFIP International Conferences on Networking。 Explanation:国际网络会议。 Publisher:IFIP。 SIT: http://dblp.uni-trier.de/db/conf/networking/index.html
专知会员服务
52+阅读 · 2020年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
最佳实践:深度学习用于自然语言处理(三)
待字闺中
3+阅读 · 2017年8月20日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2020年12月4日
Arxiv
0+阅读 · 2020年12月3日
Arxiv
6+阅读 · 2018年10月3日
Arxiv
4+阅读 · 2018年3月14日
VIP会员
相关VIP内容
专知会员服务
52+阅读 · 2020年11月3日
Top
微信扫码咨询专知VIP会员