The Library
Optimal change point detection and localization in sparse dynamic networks
Tools
Tools
Tools
Wang, Daren, Yu, Yi and Rinaldo, Alessandro (2021) Optimal change point detection and localization in sparse dynamic networks. The Annals of Statistics, 49 (1). pp. 203-232. doi:10.1214/20-AOS1953 ISSN 0090-5364.
|
PDF
WRAP-optimal-change-point-detection-localization-sparse-Yu-2020.pdf - Accepted Version - Requires a PDF viewer. Download (1023Kb) | Preview |
|
|
PDF
WRAP-supplement-2020.pdf - Unspecified Version - Requires a PDF viewer. Download (434Kb) | Preview |
Official URL: https://doi.org/10.1214/20-AOS1953
Abstract
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.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Alternative Title: | |||||||||
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Statistics | ||||||||
| Library of Congress Subject Headings (LCSH): | Change-point problems, Computer networks | ||||||||
| Journal or Publication Title: | The Annals of Statistics | ||||||||
| Publisher: | Institute of Mathematical Statistics | ||||||||
| ISSN: | 0090-5364 | ||||||||
| Official Date: | February 2021 | ||||||||
| Dates: |
|
||||||||
| Volume: | 49 | ||||||||
| Number: | 1 | ||||||||
| Page Range: | pp. 203-232 | ||||||||
| DOI: | 10.1214/20-AOS1953 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Copyright Holders: | © 2021 Institute of Mathematical Statistic | ||||||||
| Date of first compliant deposit: | 5 February 2020 | ||||||||
| Date of first compliant Open Access: | 5 February 2020 | ||||||||
| Related URLs: | |||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
