  The dynamic scaling of distributed computations plays an important role in
the utilization of elastic computational resources, such as the cloud. It
enables the provisioning and de-provisioning of resources to match dynamic
resource availability and demands. In the case of distributed graph processing,
changing the number of the graph partitions while maintaining high partitioning
quality imposes serious computational overheads as typically a time-consuming
graph partitioning algorithm needs to execute each time repartitioning is
required. In this paper, we propose a dynamic scaling method that can
efficiently change the number of graph partitions while keeping its quality
high. Our idea is based on two techniques: preprocessing and very fast edge
partitioning, called graph edge ordering and chunk-based edge partitioning,
respectively. The former converts the graph data into an ordered edge list in
such a way that edges with high locality are closer to each other. The latter
immediately divides the ordered edge list into an arbitrary number of
high-quality partitions. The evaluation with the real-world billion-scale
graphs demonstrates that our proposed approach significantly reduces the
repartitioning time, while the partitioning quality it achieves is on par with
that of the best existing static method.
