  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.
