  Graph partitioning plays a vital role in distributedlarge-scale web graph
analytics, such as pagerank and labelpropagation. The quality and scalability
of partitioning strategyhave a strong impact on such communication- and
computation-intensive applications, since it drives the communication costand
the workload balance among distributed computing nodes.Recently, the streaming
model shows promise in optimizing graphpartitioning. However, existing
streaming partitioning strategieseither lack of adequate quality or fall short
in scaling with alarge number of partitions.In this work, we explore the
property of web graph clusteringand propose a novel restreaming algorithm for
vertex-cut parti-tioning. We investigate a series of techniques, which are
pipelinedas three steps, streaming clustering, cluster partitioning,
andpartition transformation. More, these techniques can be adaptedto a parallel
mechanism for further acceleration of partitioning.Experiments on real datasets
and real systems show that ouralgorithm outperforms state-of-the-art vertex-cut
partitioningmethods in large-scale web graph processing. Surprisingly,
theruntime cost of our method can be an order of magnitude lowerthan that of
one-pass streaming partitioning algorithms, whenthe number of partitions is
large.
