  Graph partitioning drives graph processing in distributed, disk-based and
NUMA-aware systems. A commonly used partitioning goal is to balance the number
of edges per partition in conjunction with minimizing the edge or vertex cut.
While this type of partitioning is computationally expensive, we observe that
such topology-driven partitioning nonetheless results in computational load
imbalance. We propose Vertex- and Edge-Balanced Ordering (VEBO): balance the
number of edges and the number of unique destinations of those edges. VEBO
optimally balances edges and vertices for graphs with a power-law degree
distribution. Experimental evaluation on three shared-memory graph processing
systems (Ligra, Polymer and GraphGrind) shows that VEBO achieves excellent load
balance and improves performance by 1.09x over Ligra, 1.41x over Polymer and
1.65x over GraphGrind, compared to their respective partitioning algorithms,
averaged across 8 algorithms and 7 graphs.
