<p>In addition to Correlation Clustering, this is known as Clique Partitioning or Weighted Cluster Editing, see e.g. </p>

<ul>
<li>M. Grötschel and Y. Wakabayashi, <a href="http://dx.doi.org/10.1007/BF01589097" rel="nofollow">A cutting plane algorithm for a clustering problem</a>, or</li>
<li>Sebastian Böcker, Sebastian Briesemeister, and Gunnar W. Klau, <a href="http://dx.doi.org/10.1007/s00453-009-9339-7" rel="nofollow">Exact Algorithms for Cluster Editing: Evaluation and Experiments</a>.</li>
</ul>

CC BY-SA 4.0
2022-10-24T10:42:10.947Z
I need this as a hobbyist... I can't pay 40 euro for those publications without even knowing if it will help me :(.  Isn't there a publication somewhere that shows a good algorithm that is free?
Carlo Wood
CC BY-SA 3.0
2013-06-14T09:18:21.820Z
2013-06-14T14:36:14.060Z
2013-06-14T14:36:14.060Z
Falk Hüffner
<p>Has this problem been studied?</p>

<p>We start with a <em>complete</em>, simple, undirected graph with edge weights. The problem is to <em>delete edges</em> so as to partition the graph into <em>complete</em> disjoint subgraphs while maximizing the sum of the edge weights over the whole graph (deleted edges not being counted).</p>

<p>There is no constraint on the size or number of subgraphs in the solution.</p>

<p>Note this is interesting only if there are negative edge weights. Otherwise the solution would be to take the whole graph.</p>

<p>Clearly we would like to delete all the negative-weight edges while keeping all positive-weight edges, but the requirement that disjoint subgraphs be complete makes a trade-off between these goals.</p>

<p>I have seen discussion of similar graph partitioning problems but not this exact one. (Eg it is a bit like the maximum clique problem, but here I want to put every node in a disjoint clique, in the optimal way). I am guessing it is NP-complete. I am interested to know where to start looking for efficient heuristics.</p>

CC BY-SA 3.0
2013-06-14T19:48:52.337Z
Correlation clustering has been studied in the general weighted case as well. See for example erikdemaine.org/papers/Clustering_TCS/paper.pdf
Suresh Venkat
CC BY-SA 3.0
2013-06-14T01:30:10.933Z
(1) I am not sure what "complete" means here as we can WLOG fill in any graph with edges of weight zero. (2) This should be very related to the [min $k$-cut problem](http://en.wikipedia.org/wiki/Minimum_k-cut) in which we want to partition the graph into $k$ components, each connected, so as to minimize the sum of the edge weights crossing the partition boundaries. Notice that we have *Total edge weights = edge weights crossing partition + edge weights within each component*, so the objective is the same, except in that problem $k$ is given as a parameter and here you pick the best $k$.
usul
CC BY-SA 3.0
2013-06-14T05:27:27.760Z
"complete" means that within a disjoint subgraph we must keep all edges between all the nodes in that disjoint subgraph. We are not allowed to add new edges or change weights, we must use, or not use, each node in the original (complete) graph.
gareth
CC BY-SA 3.0
2013-06-14T05:42:29.150Z
This is a variant of the Correlation Clustering problem. The problem is NP-hard.
Yury
CC BY-SA 3.0
2013-06-14T05:45:32.573Z
The full list of options in the above example:
{{A}{B}{C}}=0
{{AB},{C}}=2
{{AC},{B}}=4
{{BC},{A}}=-3
{{ABC}}=3
gareth
CC BY-SA 3.0
2013-06-14T05:53:11.197Z
Yury - Aha! Thanks for that. Yes, my problem is as described here: http://en.wikipedia.org/wiki/Correlation_clustering except my weights are any real number, not constrained to {-1,+1}. Think of them as "degree of agreement (disagreement)" between vertices.
gareth
CC BY-SA 3.0
2013-06-14T05:55:39.140Z
Correction: in my first comment above I meant to say "we must use, or not use, each EDGE in the original (complete) graph." We must keep all the nodes (vertices) which are not weighted anyway.
gareth
<graph-theory><graph-algorithms>
Partition graph into complete disjoint subgraphs while maximising sum of edge weights
gareth
# Partition graph into complete disjoint subgraphs while maximising sum of edge weights

(Asked by: username_0 on 2013-06-13)

Has this problem been studied?

We start with a *complete*, simple, undirected graph with edge weights. The problem is to *delete edges* so as to partition the graph into *complete* disjoint subgraphs while maximizing the sum of the edge weights over the whole graph (deleted edges not being counted).

There is no constraint on the size or number of subgraphs in the solution.

Note this is interesting only if there are negative edge weights. Otherwise the solution would be to take the whole graph.

Clearly we would like to delete all the negative-weight edges while keeping all positive-weight edges, but the requirement that disjoint subgraphs be complete makes a trade-off between these goals.

I have seen discussion of similar graph partitioning problems but not this exact one. (Eg it is a bit like the maximum clique problem, but here I want to put every node in a disjoint clique, in the optimal way). I am guessing it is NP-complete. I am interested to know where to start looking for efficient heuristics.

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_2**: (1) I am not sure what "complete" means here as we can WLOG fill in any graph with edges of weight zero. (2) This should be very related to the [min $k$-cut problem](http://en.wikipedia.org/wiki/Minimum_k-cut) in which we want to partition the graph into $k$ components, each connected, so as to minimize the sum of the edge weights crossing the partition boundaries. Notice that we have *Total edge weights = edge weights crossing partition + edge weights within each component*, so the objective is the same, except in that problem $k$ is given as a parameter and here you pick the best $k$.  
> **username_0**: "complete" means that within a disjoint subgraph we must keep all edges between all the nodes in that disjoint subgraph. We are not allowed to add new edges or change weights, we must use, or not use, each node in the original (complete) graph.  
> **username_3**: This is a variant of the Correlation Clustering problem. The problem is NP-hard.  
> **username_0**: The full list of options in the above example: {{A}{B}{C}}=0 {{AB},{C}}=2 {{AC},{B}}=4 {{BC},{A}}=-3 {{ABC}}=3  
> **username_0**: username_3 - Aha! Thanks for that. Yes, my problem is as described here: http://en.wikipedia.org/wiki/Correlation_clustering except my weights are any real number, not constrained to {-1,+1}. Think of them as "degree of agreement (disagreement)" between vertices.  
> **username_0**: Correction: in my first comment above I meant to say "we must use, or not use, each EDGE in the original (complete) graph." We must keep all the nodes (vertices) which are not weighted anyway.  
> **username_1**: Correlation clustering has been studied in the general weighted case as well. See for example erikdemaine.org/papers/Clustering_TCS/paper.pdf  

---

## 1 answers

### Answer by username_4 on 2013-06-14. Score: 3

In addition to Correlation Clustering, this is known as Clique Partitioning or Weighted Cluster Editing, see e.g.

* M. Grötschel and Y. Wakabayashi, [A cutting plane algorithm for a clustering problem](http://dx.doi.org/10.1007/BF01589097), or
* Sebastian Böcker, Sebastian Briesemeister, and Gunnar W. Klau, [Exact Algorithms for Cluster Editing: Evaluation and Experiments](http://dx.doi.org/10.1007/s00453-009-9339-7).

> **Comments:**
> **username_5**: I need this as a hobbyist... I can't pay 40 euro for those publications without even knowing if it will help me :(.  Isn't there a publication somewhere that shows a good algorithm that is free?  

---

