Community Detection in Dynamic Networks: Exact Recovery Under Two Link Evolution Models

This paper studies edge persistence and memory in time-varying (dynamic) networks, and their effect on community detection. In particular, we focus on two models representing network memory, using which we study the asymptotic behavior of community detection in dynamic networks of large size, manifested through their phase transition threshold. In the first part, we adopt a Markovian stochastic block model (SBM) in which the edge probabilities in each network snapshot depend not only on the respective node attributes but also on the previous network snapshot. Under this model, semi-definite relaxation achieves the optimal phase transition bound for exact recovery, as observed in other community detection problems. The adverse effect of edge persistence on perfect recovery is analyzed and highlighted. In the second part, we study networks where underlying communities change slowly compared with network measurements. We model this scenario via a time series of SBM wherein the node attributes are fixed within a window of a certain size and vary independently across windows. The phase transitions are calculated via semidefinite programming which, once again, is asymptotically optimal. Numerical simulations conducted on finite-size networks interpret the asymptotic results.