  We propose Distributed Neighbor Expansion (Distributed NE), a parallel and
distributed graph partitioning method that can scale to trillion-edge graphs
while providing high partitioning quality. Distributed NE is based on a new
heuristic, called parallel expansion, where each partition is constructed in
parallel by greedily expanding its edge set from a single vertex in such a way
that the increase of the vertex cuts becomes local minimal. We theoretically
prove that the proposed method has the upper bound in the partitioning quality.
The empirical evaluation with various graphs shows that the proposed method
produces higher-quality partitions than the state-of-the-art distributed graph
partitioning algorithms. The performance evaluation shows that the space
efficiency of the proposed method is an order-of-magnitude better than the
existing algorithms, keeping its time efficiency comparable. As a result,
Distributed NE can partition a trillion-edge graph using only 256 machines
within 70 minutes.
