Weighted graph clustering with maximum size constraint

Question

I'm currently trying to solve a clustering problem. I need to cluster/partition an undirected weighted graph into groups that are restricted to size n. I have ~80000 nodes and ~260000 edges. Each node owns a weight w. The sum of all node weights in one cluster cannot exceed n. The higher the edge weight between each node, the more "valuable" it is to the cluster. Therefore, nodes with a high weight connection should end up in the same cluster and the loss if a cluster is full should be minimal. The number of clusters created is not pre specified.

I've tried implementing a min cut algorithm (Stoer-Wagner) and execute it over and over again until the size constraint is met. However, the first cut of the graph finished after >30 minutes and created sub-graph consisted of only one node.

Are there any solutions to this problem considering the size constraint? Is there a way to extend a min-cut algorithm to solve this?

Thanks in advance!

Answer 1

I can't think of an exact algorithm and don't know if an efficient one exists. But if you're ok with heuristics and approximate solutions you could try the following:

Find an initial solution:

Repeat the following until every vertex is assigned to a cluster:

Pick a vertex u belonging to no cluster and create a new cluster C = {u0}. Grow a minimum weight tree from {u0} using Prim's algorithm (using only vertices assigned to no cluster) with a cost function corresponding to:

C[v] = minimum over (u=neighbour of v in C) of -value((u,v))/weight(v)

(you just have to adapt the cost update function of any efficient Prim implementation)

Stop when the weight of your Tree starts getting too big.

That's just an idea. You could also try to start with any random assignment of clusters which agrees with the weight constraint.

Perform local optimizations:

Pick a vertex v and see if you can gain value by moving it to another cluster by computing the sum of values of the edges you gain minus the sum of the edges you loose. Pick the cluster which maximizes this sum, among the ones which are possible (i.e, weight(C) + weight(v) <= n). You can repeat that as long as you like or as long as the solution is improving, choosing the vertices in some order or randomly.

If this doesn't work well enough, you can allow to sometimes perform swaps which make your solution momentarily worse in order to get out of a local minimum, using something like Simulated annealing or Tabu Search.