Dynamic Spectral Clustering with Provable Approximation Guarantee
This provides an efficient solution for clustering evolving networks, though it appears incremental as it adapts spectral clustering to dynamic settings with theoretical guarantees.
The paper tackles the problem of clustering dynamically evolving graphs where edges and vertices are added over time, proving that a dynamic variant of spectral clustering can approximate the final graph's clusters with amortized O(1) update time and sublinear query time.
This paper studies clustering algorithms for dynamically evolving graphs $\{G_t\}$, in which new edges (and potential new vertices) are added into a graph, and the underlying cluster structure of the graph can gradually change. The paper proves that, under some mild condition on the cluster-structure, the clusters of the final graph $G_T$ of $n_T$ vertices at time $T$ can be well approximated by a dynamic variant of the spectral clustering algorithm. The algorithm runs in amortised update time $O(1)$ and query time $o(n_T)$. Experimental studies on both synthetic and real-world datasets further confirm the practicality of our designed algorithm.