Dynamic Structural Clustering on Graphs

Abstract

\em Structural Clustering ($\strclu$) is one of the most popular graph clustering paradigms. In this paper, we consider $\strclu$ under Jaccard similarity on a dynamic graph, G = (V, E), subject to edge insertions and deletions (updates). 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 cost is~O(|V|) per update; we improve this update-time bound \em significantly with the ρ-approximate notion. Specifically, for a specified failure probability, δ^*, and \em every sequence of~M updates (no need to know M's value in advance), our algorithm, $\dynelm$, achieves~O(?og^2 |V| + og |V| \cdot ?og \fracM ?^* )$ amortized cost for each update, \em at all times in linear space. Moreover, $\dynelm$ provides a provable "sandwich'' guarantee on the clustering quality at all times after each update with probability at least 1 - ^*. We further develop dynelm into our ultimate algorithm, dynstr, which also supports \em cluster-group-by queries. Given Q \subseteq V, this puts the non-empty intersection of Q and each strclu cluster into a distinct group. dynstr not only achieves all the guarantees of dynelm, but also runs \em cluster-group-by queries in~O(|Q|\cdot og |V|) time. We demonstrate the performance of our algorithms via extensive experiments, on 15 real datasets. Experimental results confirm that our algorithms are up to three orders of magnitude more efficient than state-of-the-art competitors, and still provide quality structural clustering results.

Topics & Concepts