Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908388109058048 |
|---|---|
| author | Shakiba, Ali |
| author_facet | Shakiba, Ali |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_00384 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach Shakiba, Ali Data Structures and Algorithms Machine Learning 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. |
| title | Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2301.00384 |