Weakly Negative Circles Versus Best Clustering in Signed Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913342591860736 |
|---|---|
| author | Gottstein, Michael G. Parsaei-Majd, Leila Zaslavsky, Thomas |
| author_facet | Gottstein, Michael G. Parsaei-Majd, Leila Zaslavsky, Thomas |
| contents | Clustering a signed graph means partitioning the vertices into sets ("clusters") so that every positive edge, and no negative edge, is within a cluster. Clustering is not always possible; the obstruction is circles with exactly one negative edge ("weakly negative circles"). The correlation clustering problem is to cluster with the minimum number of edges that violate the clustering rule, called $Q$. A lower bound is $w$, the maximum number of edge-disjoint weakly negative circles. If every two such circles are edge disjoint, then $Q=w$. We characterize signed graphs of this kind. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_03114 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Weakly Negative Circles Versus Best Clustering in Signed Graphs Gottstein, Michael G. Parsaei-Majd, Leila Zaslavsky, Thomas Combinatorics 05C22 Clustering a signed graph means partitioning the vertices into sets ("clusters") so that every positive edge, and no negative edge, is within a cluster. Clustering is not always possible; the obstruction is circles with exactly one negative edge ("weakly negative circles"). The correlation clustering problem is to cluster with the minimum number of edges that violate the clustering rule, called $Q$. A lower bound is $w$, the maximum number of edge-disjoint weakly negative circles. If every two such circles are edge disjoint, then $Q=w$. We characterize signed graphs of this kind. |
| title | Weakly Negative Circles Versus Best Clustering in Signed Graphs |
| topic | Combinatorics 05C22 |
| url | https://arxiv.org/abs/2405.03114 |