Recovering communities in temporal networks using persistent edges

Abstract

This article studies the recovery of static communities in a temporal network. We introduce a temporal stochastic block model where dynamic interaction patterns between node pairs follow a Markov chain. We render this model versatile by adding degree correction parameters, describing the tendency of each node to start new interactions. We show that in some cases the likelihood of this model is approximated by the regularized modularity of a time-aggregated graph. This time-aggregated graph involves a trade-off between new edges and persistent edges. A continuous relaxation reduces the regularized modularity maximization to a normalized spectral clustering. We illustrate by numerical experiments the importance of edge persistence, both on simulated and real data sets.