PowerLore NIPS’14: paper code

PowerLore是一个高效的处理power-law图的分布式框架。

• degree-based hashing algorithm (Libra)，提供了理论证明。
• two degree-based greedy algorithm (Constell and Zodiac)

Graph Partition

Edge-cut

Edge-cut tries to evenly assign vetices to machines bu cutting edge. Both machines of a cut edge should maintain a ghost (local replica) of the vertex and the edge data.

The workload of a machine is determined by the number of vetices located in that machine.

The communication cost of the whole graph is determined by the number of edges spanning different machines.

Vetex-cut

Vetex-cut tries to evenly assign the edges to machines bu cutting the vertices. All the machines associated with a cut vetex should maintain a mirror (local replica) of the vertex.

The workload of a machine is determind by the number of edges located in that machine.

The communication cost of the whole graph is determined by the number of mirrors of the vertices.

Degree-based Hasing Algorithm

Libra使用$vetex_hash$函数来定义$edge_hash$，将边分给度数小的点所在的分区。(We name this algorithm by Libra, because it weighs the degrees of the two ends of each edge, which behaves like a pair of scales)。