Abstract Recently, distributed processing of large dynamic graphs has become very popular, especially in certain domains such as social network analysis, Web graph analysis and spatial network analysis. In this context, many distributed parallel graph processing systems have been proposed, such as Pregel, PowerGraph, GraphLab, and Trinity. However, these systems deal only with static graphs and do not consider the issue of processing evolving and dynamic graphs. In this paper, we are considering the issues of scale and dynamism in the case of graph processing systems. We present bladyg , a graph processing framework that addresses the issue of dynamism in large-scale graphs. We present an implementation of bladyg on top of akka framework. We experimentally evaluate the performance of the proposed framework by applying it to problems such as distributed k-core decomposition and partitioning of large dynamic graphs. The experimental results show that the performance and scalability of bladyg are satisfying for large-scale dynamic graphs.
GraphLab @cite_16 is a graph processing framework that share the same motivation with Pregel. While pregel targets Google's large distributed system, GraphLab addresses shared memory parallel systems which means that there is more focus on parallel access of memory than on the issue of efficient message passing and synchronization. In the programming model of GraphLab, the users define an update function that can change all data associated to the scope of that node (its edges or its neighbors). Figure shows the scope of a vertex: an update function called on that vertex will be able to read and write all data in its scope. We notice that that scopes can overlap, so simultaneously executing two update functions can result in a collision. In this context, GraphLab offers some consistency models in order to allow its users to trade off performance and consistency as appropriate for their computation. As described in Figure , GraphLab offers a fully consistent model, a vertex consistent model or an edge consistent model.
@cite_16
2096544401
While high-level data parallel frameworks, like MapReduce, simplify the design and implementation of large-scale data processing systems, they do not naturally or efficiently support many important data mining and machine learning algorithms and can lead to inefficient learning systems. To help fill this critical void, we introduced the GraphLab abstraction which naturally expresses asynchronous, dynamic, graph-parallel computation while ensuring data consistency and achieving a high degree of parallel performance in the shared-memory setting. In this paper, we extend the GraphLab framework to the substantially more challenging distributed setting while preserving strong data consistency guarantees. We develop graph based extensions to pipelined locking and data versioning to reduce network congestion and mitigate the effect of network latency. We also introduce fault tolerance to the GraphLab abstraction using the classic Chandy-Lamport snapshot algorithm and demonstrate how it can be easily implemented by exploiting the GraphLab abstraction itself. Finally, we evaluate our distributed implementation of the GraphLab abstraction on a large Amazon EC2 deployment and show 1-2 orders of magnitude performance gains over Hadoop-based implementations.