Partitioning weighted graph into equally weighted groups

I have a bidirectional graph with weighted edges and weighted vertices. I want to find N groups of disjoint, connected vertices so that:

1. the summed weights of each group are close to, but not greater than a certain value TargetWeight
2. the weight of the selected edges to form these groups is as low as possible. One catch here: the weight of an edge can decrease if another edge is also chosen (A portion of the weight is shared between the edges). One example: edge E1 has weight 20, edge E2 has weight 30, they share a weight of 5. Taking only E1 will result in weight 20, taking both E1 and E2 will result in combined weight of 45 (the shared weight is only taken into account once).

N is known in advance, but is allowed to be greater if results would improve greatly.

TargetWeight is known in advance, there is no real metric available when multiple smaller groups with low cost are better than a big group with high cost.

The graph has around 50k nodes in a typical case. The graph is not stored in a database.

You can look at this problem as a clustering algorithm, but the general discussions about clustering can differ a开发者_JAVA百科lot from what I need. I have tried a KMeans algorithm, but I found the result not good enough. Right now I am using an exploration based heuristic that checks how good a certain choice influences future choices of groups. This approach works, but is quite slow.

I think the best way to deal with this kind of problem is:

• First: define a cost function base on you're 2 criterias:

  Cost(graph) = SUM(Distance(subgraphweight,TargetWeight)) + SUM(WeightEdges(subgraph)) where distance(x,y) is very large if x>y and equal to y-x otherwise

• Second: Partition the graph randomly into N(or more) groups of disjoint subgraph

• third: go through the graph and move one vertices from one group to another and check if the total cost will decrease