Network Performance Aware Graph Partitioning for Large Graph Processing Systems in the Cloud - Large Scale and Big Data: Processing and Management - page 242

That means, we have C ( n 1 , n 2 ) + C ( n 3 , n 4 ) ≥ C ( n π(1) , n π(2) ) + C ( n π(3) , n π(4) ) where π is
any permutation on (1, 2, 3, 4). □
The intuition of the proximity is, at a certain level of the ideal partition sketch, the
partitions with a low common ancestor have a larger number of cross-partition edges
than those with a high common ancestor.
These properties of the partitioning sketch indicate the following design prin-
ciples for graph partitioning and processing, to match the network bandwidth with
the number of cross-partition edges.
P 1 . Graph partitioning and processing should gracefully adapt to the bandwidth
unevenness in the cloud network. The number of cross-partition edges is a
good indicator on bandwidth requirements. According to the local optimal-
ity, the two partitions generated in a bisection on a graph should be stored
on two machine sets such that the total bandwidth between the two machine
sets is the lowest.
P 2 . The partition size should be carefully chosen for the efficiency of process-
ing. The number of partitions should be no smaller than the number of
machines available for parallelism. According to the monotonicity, a small
partition size increases the number of levels of the partition sketch, result-
ing in a large number of cross-partition edges. On the other hand, a large
partition may not fit into main memory of a machine, which results in ran-
dom disk I/O in accessing the graph data.
P 3 . According to proximity, the nodes with a low common ancestor should be
stored together in the machine sets with high interconnected bandwidth
to reduce the performance impact of the large number of cross-partition
edges.
7.5.3 b anDwiDth a ware g raPh P artitioning
The network bandwidth aware framework for graph partitioning and processing
in the cloud exploits the ideal partition sketch and the machine graph discussed in
Sections 7.5.1 and 7.5.2, which enhances a popular multilevel graph partitioning
algorithm with the network performance awareness . This subsection presents some
design issues and an overview of such a framework.
7.5.3.1 Background on the Bisection in the Multilevel Graph Partitioning
Since graph bisection has been a key operation in multilevel graph partitioning
[44,46], we briefly introduce the process of bisection. There are three phases in
a graph bisection, namely coarsening , partitioning , and uncoarsening , as illus-
trated in Figure 7.4. The coarsening phase consists of multiple iterations. In each
iteration, multiple adjacent vertices in the graph are coarsened into one according
to some heuristics, and the graph is condensed into a smaller graph. The coars-
ening phase ends when the graph is small enough, in the scale of thousands of
vertices. The partitioning phase divides the coarsened graph into two partitions