SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2301.00384 · 2023

Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

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.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2301.00384")
get_code_for_paper("2301.00384")
have("2301.00384")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2301.00384.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2301.00384.svg)](https://syntology.ai/paper/2301.00384)

Connect an agent — have() is free.