|
| | | | |
| | | |
| Stat |
Members: 3665
Articles: 2'599'751
Articles rated: 2609
21 January 2025 |
|
| | | | |
|
Article overview
| |
|
|
Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach | | Ali Shakiba
; | | Date: |
1 Jan 2023 | | Abstract: | In this paper, we reduce the complexity of approximating the correlation
clustering problem from $O(m imesleft( 2+ alpha (G)
ight)+n)$ to $O(m+n)$
for any given value of $varepsilon$ for a complete signed graph with $n$
vertices and $m$ positive edges where $alpha(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 imesalpha(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. | | Source: | arXiv, 2301.00384 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER