This paper presents a novel index-based approach to improve the runtime and extend the applicability of approximation algorithms for correlation clustering on complete signed graphs. Building on prior work, we introduce an indexing structure that enhances runtime efficiency and enables full dynamic updates, including vertex addition, removal, and edge sign flipping. For a complete graph with n vertices and m positively signed edges, our method achieves an amortized runtime of \(\mathcal {O}(m \cdot \alpha (n))\) for dynamic operations and \(\mathcal {O}(m + n)\) for clustering queries with a fixed threshold \(\varepsilon \) , while pre-computation scales as \(\mathcal {O}(m \cdot (\alpha (G) + \log m))\) where \(\alpha (G)\) is the arboricity of the graph. The overhead memory cost for the index is \(\mathcal {O}\left( m+n\right) \) . The proposed method retains the theoretical guarantees of prior algorithms and addresses their computational bottlenecks. Extensive experiments on seven real-world datasets validate the practical efficiency of the approach, showing a 34% decrease in clustering runtime on average compared to non-indexed methods. These results demonstrate the scalability and adaptability of the method for large-scale and dynamic graph clustering scenarios.
