As we had mentioned earlier, graph processing becomes challenging when we use disk-partitioning strategies employed in MapReduce and others. Let's elaborate on this topic a little; we won't go into too much detail.
The problem is when we have millions of vertices and edges that do not fit into one machine, which means we need a distributed storage scheme. Naturally, we will have to store vertices and edges in many machines. Then the challenge is running iterative algorithms that would need back and forth communication between the machines. Interestingly, a Giraffe graph lends itself to efficient partitioning—one can cut the graph at the neck. So in our example, we can store the vertices A, B, and C in one machine and D, E, F, and G in another machine and still have optimum communication. This is called the edge cut. Unfortunately, the large graphs we encounter are all long-tail-based, that is, a few vertices are very popular and have lots of connections. In such cases,...
