ABSTRACT
The scale of graph data that is nowadays collected and required to be processed is massive. For example, in the context of online services, the web graph amounts to at least 1 trillion of links [1]. Facebook recently reported more than 1 billion of users and 140 billion of friend connections [2], and Twitter reported in 2009 more than 40 million of users and about 1.5 billion of social relations [30]. The unprecedented proliferation of data provides us with new opportunities and benets but also poses hard computational challenges. Frequent graph computations such as community detection [25], nding connected components [29], iterative computations using graph input data such as computing PageRank and its variations [41], and shortest path and radius computations [17,28] become challenging computational tasks in the realm of big graph data.
