249Network Performance Aware Graph Partitioning
7.7.5 DistributeD graPh Partitioning algorithms
Prior to the network bandwidth aware framework described in the previous sec-
tions, distributed graph partitioning [24,47,52] was the traditional way of reducing
data shufing in distributed graph processing. The commonly used distributed graph
processing algorithms are multilevel algorithms [44,46,73], which are also used in
the partitioning algorithm described in this chapter. They have been proved efcient
in many applications.
7.7.6 the metis Framework
A highly popular tool Metis [47] is a multilevel graph partitioning framework whose
implementation is fast, robust, and easy to use. The multilevel graph partitioning
framework contains three ...