  In the realm of distributed systems tasked with managing and processing
large-scale graph-structured data, optimizing graph partitioning stands as a
pivotal challenge. The primary goal is to minimize communication overhead and
runtime cost. However, alongside the computational complexity associated with
optimal graph partitioning, a critical factor to consider is memory overhead.
Real-world graphs often reach colossal sizes, making it impractical and
economically unviable to load the entire graph into memory for partitioning.
This is also a fundamental premise in distributed graph processing, where
accommodating a graph with non-distributed systems is unattainable. Currently,
existing streaming partitioning algorithms exhibit a skew-oblivious nature,
yielding satisfactory partitioning results exclusively for specific graph
types. In this paper, we propose a novel streaming partitioning algorithm, the
Skewness-aware Vertex-cut Partitioner S5P, designed to leverage the skewness
characteristics of real graphs for achieving high-quality partitioning. S5P
offers high partitioning quality by segregating the graph's edge set into two
subsets, head and tail sets. Following processing by a skewness-aware
clustering algorithm, these two subsets subsequently undergo a Stackelberg
graph game. Our extensive evaluations conducted on substantial real-world and
synthetic graphs demonstrate that, in all instances, the partitioning quality
of S5P surpasses that of existing streaming partitioning algorithms, operating
within the same load balance constraints. For example, S5P can bring up to a
51% improvement in partitioning quality compared to the top partitioner among
the baselines. Lastly, we showcase that the implementation of S5P results in up
to an 81% reduction in communication cost and a 130% increase in runtime
efficiency for distributed graph processing tasks on PowerGraph.
