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
~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!