Changepoint Estimation in Sparse Dynamic Stochastic Block Models under Near-Optimal Signal Strength

We consider the offline changepoint estimation problem in the context of multilayer stochastic block models. We develop an algorithm involving suitably chosen CUSUM statistics based on the adjacency matrices of the observed networks for estimating a single changepoint present in the input data. We provide rigorous theoretical guarantees on the performance of the proposed method when one or more of the following phenomena occur at the changepoint: (a) merging of communities, (b) splitting of communities, and (c) changes in the connection probabilities among the communities. We derive a lower bound on the minimax detectability threshold involving the relevant signal strength parameter and show that the proposed algorithm can estimate the changepoint consistently when the signal strength is above a small multiplicative factor times the minimax detectability threshold. We do not make any a priori assumption on the sparsity of the underlying networks and only require that the overall average degree goes to infinity. Via simulation experiments, we empirically show that the proposed algorithm works in regimes of signal strength where global network changepoint estimation algorithms that do not take into account the community structure, fail to estimate an existing changepoint correctly. Finally, we apply our algorithm to a series of networks constructed using roll call data from the US senate and obtain changepoint(s) which align with those reported in the political science literature regarding the phenomenon of increasing political polarization.