  Distributed graph platforms like Pregel have used vertex- centric programming
models to process the growing corpus of graph datasets using commodity
clusters. The irregular structure of graphs cause load imbalances across
machines operating on graph partitions, and this is exacerbated for
non-stationary graph algorithms such as traversals, where not all parts of the
graph are active at the same time. As a result, such graph platforms, even as
they scale, do not make efficient use of distributed resources. Clouds offer
elastic virtual machines that can be leveraged to improve the resource
utilization for such platforms and hence reduce the monetary cost for their
execution. In this paper, we propose strategies for elastic placement of graph
partitions on Cloud VMs for subgraphcentric programming model to reduce the
cost of execution compared to a static placement, even as we minimize the
increase in makespan. These strategies are innovative in modeling the graph
algorithms behavior. We validate our strategies for several graphs, using
runtime tra- ces for their distributed execution of a Breadth First Search
(BFS) algorithms on our subgraph-centric GoFFish graph platform. Our strategies
are able to reduce the cost of exe- cution by up to 42%, compared to a static
placement, while achieving a makespan that is within 29% of the optimal

Distributed, Parallel, and Cluster Computing