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