Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach
This work addresses the problem of efficiently approximating correlation clustering in dynamic settings for researchers and practitioners in graph algorithms, though it is incremental as it builds on existing methods with specific optimizations.
The paper tackles the correlation clustering problem for dynamic complete signed graphs by reducing the approximation complexity from O(m×(2+α(G))+n) to O(m+n) for any ε, while maintaining the same output and enabling full dynamic updates like edge sign flipping and vertex addition/removal. The index-based algorithm shows a 34% average time decrease in experiments on seven real-world graphs.
In this paper, we reduce the complexity of approximating the correlation clustering problem from $O(m\times\left( 2+ α(G) \right)+n)$ to $O(m+n)$ for any given value of $\varepsilon$ for a complete signed graph with $n$ vertices and $m$ positive edges where $α(G)$ is the arboricity of the graph. Our approach gives the same output as the original algorithm and makes it possible to implement the algorithm in a full dynamic setting where edge sign flipping and vertex addition/removal are allowed. Constructing this index costs $O(m)$ memory and $O(m\timesα(G))$ time. We also studied the structural properties of the non-agreement measure used in the approximation algorithm. The theoretical results are accompanied by a full set of experiments concerning seven real-world graphs. These results shows superiority of our index-based algorithm to the non-index one by a decrease of %34 in time on average.