Spectral clustering in the dynamic stochastic block model
This work addresses community tracking in evolving networks, but it appears incremental as it adapts existing spectral clustering to a dynamic setting with smoothness assumptions.
The authors tackled the problem of community detection in dynamic networks by proposing a spectral clustering method for the Dynamic Stochastic Block Model, achieving non-asymptotic guarantees for estimation and clustering precision.
In the present paper, we studied a Dynamic Stochastic Block Model (DSBM) under the assumptions that the connection probabilities, as functions of time, are smooth and that at most $s$ nodes can switch their class memberships between two consecutive time points. We estimate the edge probability tensor by a kernel-type procedure and extract the group memberships of the nodes by spectral clustering. The procedure is computationally viable, adaptive to the unknown smoothness of the functional connection probabilities, to the rate $s$ of membership switching and to the unknown number of clusters. In addition, it is accompanied by non-asymptotic guarantees for the precision of estimation and clustering.