Exact Recovery Threshold in Dynamic Binary Censored Block Model

This paper considers community detection in the dynamic binary censored block model. Under this model, the graph is observed at successive times (snapshots), and the node label in the current snapshot is dependent on the same node label in the previous τ snapshots. In this paper, the maximum likelihood estimator of the current node labels is obtained under this model, subject to the observation of the graph in the present and past snapshots, and the exact recovery conditions are derived. Relaxing the maximum likelihood estimator, a semidefinite programming algorithm is proposed for community detection. In the asymptotic regime, a sufficient condition for exact recovery is obtained using the semidefinite programming estimator, which is shown to asymptotically match the sufficient conditions for exact recovery.