Correlation Clustering for General Graphs
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909687199301632 |
|---|---|
| author | Parsaei-Majd, Leila |
| author_facet | Parsaei-Majd, Leila |
| contents | Correlation clustering provides a method for separating the vertices of a signed graph into the optimum number of clusters without specifying that number in advance. The main goal in this type of clustering is to minimize the number of disagreements: the number of negative edges inside clusters plus the number of positive edges between clusters. In this paper, we present an algorithm for correlation clustering in general case. Also, we show that there is a necessary and sufficient condition under which the lower bound, maximum number of edge disjoint weakly negative cycles, is equal to minimum number of disagreements. Finally, we prove that the presented algorithm gives a $2$-approximation for a subclass of signed graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_09576 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Correlation Clustering for General Graphs Parsaei-Majd, Leila Combinatorics Correlation clustering provides a method for separating the vertices of a signed graph into the optimum number of clusters without specifying that number in advance. The main goal in this type of clustering is to minimize the number of disagreements: the number of negative edges inside clusters plus the number of positive edges between clusters. In this paper, we present an algorithm for correlation clustering in general case. Also, we show that there is a necessary and sufficient condition under which the lower bound, maximum number of edge disjoint weakly negative cycles, is equal to minimum number of disagreements. Finally, we prove that the presented algorithm gives a $2$-approximation for a subclass of signed graphs. |
| title | Correlation Clustering for General Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.09576 |