Newbie question - What is balance?


I have recently started using Metis to partition some sparse graphs with weighted edges. When I run the software it gives me two values: edge-cut and balance. I understand what edge-cut is, but I could not find a precise definition of "balance" in the manual. I assume it refers to the sizes of the partitions being similar, however I would like an exact definition and want to know how it is computed. Thank you for your help.

RE: Let k be the number of

Let k be the number of partitions, W_i the sum of the weights of the vertices assigned to partition i,
and W be the sum of the weight of all the vertices.

balance = k*max_i(W_i)/W

RE: Thanks

Thanks a lot!