Streaming edge partitioning plays a crucial role in the distributed processing of large-scale web graphs, such as pagerank. The quality of partitioning is of utmost importance and directly affects the runtime cost of distributed graph processing. However, streaming graph clustering, a key component of mainstream streaming edge partitioning, is vertex-centric. This incurs a mismatch with the edge-centric partitioning strategy, necessitating additional post-processing and several graph traversals to transition from vertex-centric clusters to edge-centric partitions. This transition not only adds extra runtime overhead but also risks a decline in partitioning quality. In this paper, we propose a novel algorithm, called ClusPar, to address the problem of streaming edge partitioning. The ClusPar framework consists of two steps, streaming edge clustering and edge cluster partitioning. Different from prior studies, the first step traverses the input graph in a single pass to generate edge-centric clusters, while the second step applies game theory over these edge-centric clusters to produce partitions. Extensive experiments show that ClusPar outperforms the state-of-the-art streaming edge partitioning methods in terms of the partitioning quality, efficiency, and scalability.

Graph partitioning plays a vital role in distributed large-scale web graph analytics, such as pagerank and label propagation. The quality and scalability of partitioning strategy have a strong impact on such communication- and computation-intensive applications, since it drives the communication cost and the workload balance among distributed computing nodes. Recently, the streaming model shows promise in optimizing graph partitioning. However, existing streaming partitioning strategies either lack of adequate quality or fall short in scaling with a large number of partitions. In this work, we explore the property of web graph clustering and propose a novel restreaming algorithm for vertex-cut partitioning. We investigate a series of techniques, which are pipelined as three steps, streaming clustering, cluster partitioning, and partition transformation. More, these techniques can be adapted to a parallel mechanism for further acceleration of partitioning. Experiments on real datasets and real systems show that our algorithm outperforms state-of-the-art vertex-cut partitioning methods in large-scale web graph processing. Surprisingly, the runtime cost of our method can be an order of magnitude lower than that of one-pass streaming partitioning algorithms, when the number of partitions is large.