Dynamic Structural Clustering on Graphs
Citations Over TimeTop 13% of 2021 papers
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.
Related Papers
- → Improving Jaccard Index for Measuring Similarity in Collaborative Filtering(2017)27 cited
- → Improving Jaccard Index Using Genetic Algorithms for Collaborative Filtering(2017)5 cited
- → Comparison of Similarity Coefficients on Morphological Rodent Tuber(2018)9 cited
- → Utilization of Jaccard Index Measures on Multiple Attribute Group Decision Making under Neutrosophic Environment(2020)3 cited
- → Jaccard Distance (Jaccard Index, Jaccard Similarity Coefficient)(2004)51 cited