Dynamic Structural Clustering on Graphs

Structural Clustering (StrClu) is one of the most popular graph clustering paradigms. In this paper, we consider StrClu under the Jaccard similarity on a dynamic graph, G = < V, E >, subject to edge insertions and deletions. The goal is to maintain certain information under updates, so that the StrClu clustering result on G can be retrieved in O(|V| + |E|) time, upon request. The state-of-the-art worst-case update cost is O(|V|). We improve this bound significantly with the \rho-approximate notion. Specifically, for any sequence of updates that satisfies: for every vertex u in V, the frequency of deletions incident on u is at most a constant fraction of that of the insertions incident on u, our algorithm, DynELM, achieves ~O(1) amortized cost for each update, with linear space consumption, where the notation ~O( ) hides a poly-logarithmic factor in the complexity. Moreover, DynELM provides a provable "sandwich" guarantee on the clustering quality with high probability. We further develop DynELM into our ultimate algorithm, DynStrClu, which also supports cluster-group-by queries. Given an arbitrary subset Q of V, this puts the non-empty intersection of Q and each StrClu cluster into a distinct group. DynStrClu not only achieves all the guarantees of DynELM, but also runs cluster-group-by queries in ~O(|Q|) time. We demonstrate the performance of our algorithms via extensive experiments, on 14 real datasets. Experimental results confirm that both our algorithms are up to three orders of magnitude more efficient than state-of-the-art competitors, and still provide quality structural clustering results.