
239Network Performance Aware Graph Partitioning
partitioning and graph processing algorithm aware of the bandwidth unevenness for
networking efciency.
Foremost, graph partitioning has been a classical combinatorial optimization
problem, with an input objective function. The input objective function is to mini-
mize the number of cross-partition edges with the constraint of all partitions with
similar number of edges. This is because the total number of cross-partition edges
is often a good indicator of the amount of communication between partitions in dis-
tributed computation. It is an NP-complete problem [50].
The network performance aware g