How to partition a graph into N groups with M elements nearest? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T14:35:48Z http://mathoverflow.net/feeds/question/103888 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103888/how-to-partition-a-graph-into-n-groups-with-m-elements-nearest How to partition a graph into N groups with M elements nearest? Bruno Caponi 2012-08-03T18:12:35Z 2013-05-03T12:22:00Z <p>Hi.</p> <p>This problem probably already here but I could not find the right words to find it.</p> <p>I have a list with 1700 points (geographic coordinates) and a need to separate into 17 groups with 100 nearest. I mapped this as a graph where each node is the point and each edge weight is the real distance of points connected by this. Then the problem is how to partition this graph into 17 groups of 100 elements each that minimizes the sum of the inter-partition edges weight.</p> <p>Someone has a better idea to map this problem? </p> <p>I tried to use METIS but the best result was using the edge-cut that minimize the sum of the weights of the edges removed (for this case I use the inverse of the distance as weight). I also tried using k-means but it does not guarantee the number of elements in each group.</p> <p>Thanks in advance!</p> http://mathoverflow.net/questions/103888/how-to-partition-a-graph-into-n-groups-with-m-elements-nearest/104216#104216 Answer by Andrew D. King for How to partition a graph into N groups with M elements nearest? Andrew D. King 2012-08-07T18:15:12Z 2012-08-07T18:15:12Z <p>Unfortunately I have just an approach, not a tool for you to use.</p> <p>I would suggest using a local search algorithm that maintains the size of the sets at 100. You seek a <em>clustering</em> that consists of a partition of the vertices int 17 clusters, each of size 100. The <em>cost</em> of each cluster is the sum over all pairs of vertices in the cluster of the distance between the vertices. The cost of a clustering is the sum of the 17 cluster costs.</p> <p>Your <em>move</em> in the local search space should be exchanging a vertex in one cluster with a vertex in another cluster. In this way you can compute the change in cost that results from exchanging two vertices.</p> <p>Depending on how you select a move, this may be very time consuming. If you try this kind of approach, you might want to do it on 10% of the data set just to make sure it's not going to take an absurd amount of time to find a decent solution.</p>