In the trend of social media, graph is frequently mentioned as a common description of social network/friend circle/work connection in real-life. But graph can be really large and hard to store in one server. Therefore, distributed clusters/systems are here to help.

Typical graph processing

Each node is assigned with a value, in each iteration, it gather values from its immediate neighbors and does some computation using its own value and neighbor value to generate new value. After that, update its new value and send it out to neighbors.

Distributed graph processing

Assign each vertex to one server. Then, each server thus gets a subset of vertices since a server might get several assigned vertices.

Then, they do typical Gather-Apply-Scatter for all assigned vertices.

For assigning process, it can based on different options, such as hash-based or locality-based (assign related neighbor to the same server).

Pregel System by Google

In execution, it can be described as:

In case of failure, each server save the state of their vertices periodically to generate “checkpoint” in permanent storage, so that they can retrieve after recovery.

Small World Network

High cluster coefficient (CC), short path (path length of shortest path).

Distribution of degree

the probability of a given node has k edges can follow different distribution, such as:

A lot of small world networks are power law graphs, but not all.