Newbie question - What is balance?
Hi,
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.
Submitted by avalon on Wed, 2008-10-29 00:15
»
- Login to post comments
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!