Cut to Fit: Tailoring the Partitioning to the Computation

Social Graph Analytics applications are very often built using off-the-shelf analytics frameworks. These, however, are profiled and optimized for the general case and have to perform for all kinds of graphs. This paper investigates how knowledge of the application and the dataset can help optimize performance with minimal effort. We concentrate on the impact of partitioning strategies on the performance of computations on social graphs. We evaluate six graph partitioning algorithms on a set of six social graphs, using four standard graph algorithms by measuring a set of five partitioning metrics. We analyze the performance of each partitioning strategy with respect to (i) the properties of the graph dataset, (ii) each analytics computation,of partitions. We discover that communication cost is the best predictor of performance for most -but not all- analytics computations. We also find that the best partitioning strategy for a particular kind of algorithm may not be the best for another, and that optimizing for the general case of all algorithms may not select the optimal partitioning strategy for a given graph algorithm. We conclude with insights on selecting the right data partitioning strategy, which has significant impact on the performance of large graph analytics computations; certainly enough to warrant optimization of the partitioning strategy to the computation and to the dataset.