I'm looking for an algorithm to cluster weighted directed graphs that have weights on both edges and vertices. I'm using graphs with multiple weights(labels) on vertices and a weight on edges that represent the communication cost of elements. The result should be multiple connected subgraphs(clusters) that has the minimum communication cost between clusters(kind of similar to min k-cut) and the weight of elements inside each cluster should be balanced among others.
I found out that METIS is a great tool for partitioning graphs the way i want! but the number of partitions should be provided for algorithm to work, but in my case i don't know the number of partitions and i just want to partition the graph based on weights and i expect the algorithm to determine number of partitions based on weights on edges and vertices and i want it to find the (near)optimum solution.
Any suggestion would be greatly appreciated.