Spectral clustering in the dynamic stochastic block model

2017/05/02 by Marianna Pensky, Teng Zhang, Pensky, Marianna +1 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #05C80 #Bayesian Methods and Mixture Models #Complex Network Analysis Techniques #FOS: Computer and information sciences #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Methodology (stat.ME) #Primary: 62F12. Secondary: 62H30

paper · pdf · doi:10.48550/arxiv.1705.01204

openalex publication_date 2017/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Fast community detection by SCORE
• A tutorial on spectral clustering

Cited by

• Dependent stochastic block models for age-indexed sequences of directed causes-of-death networks

Related

• Sparse and Smooth: improved guarantees for Spectral Clustering in the Dynamic Stochastic Block Model
• Strong Consistency of Spectral Clustering for Stochastic Block Models
• Statistical clustering of temporal networks through a dynamic stochastic block model
• Dynamic clustering for heterophilic stochastic block models with time-varying node memberships
• A spectral method for community detection in moderately-sparse degree-corrected stochastic block models