Exact Recovery Thresholds in Dynamic Binary Censored Block Models
Javad Zahedi Moghaddam
Abstract:
This study considers community detection in the dynamic binary censored block model. Under this model, the probabilistic estimator of the current node labels is obtained given the observation of the graph at successive times (snapshots). To address the NP-hardness and intractability of the estimator, we relax some constraints and propose a semidefinite programming algorithm for dynamic community detection. In the asymptotic regime, a sufficient condition for exact recovery is obtained for the proposed method, which is shown to asymptotically match the sufficient conditions for exact recovery.