A Multi-source Message Passing Model to Improve the Parallelism Efficiency of Graph Mining on MapReduce

The MapReduce framework has been employed in many papers to process the large-scale graph. In this paper, we propose a multi-source message passing model to achieve multi-source traversal of graph in one iterative progress, which largely improve the parallelism efficiency of graph algorithm involving multi-source traversal which occurs in many complex graph algorithms. As the model can traverse the graph from different sources in one iterative progress, the multi-source traversal will finish in much less iteration than before. In this way, the total runtime of the algorithm involves multi-source traversal will be reduced in a large scale. Besides, the message passing model is flexible enough to express a broad set of algorithms. Hence, we design the interface of message passing to facilitate using our model to develop algorithms. Finally, the experiment shows the efficiency and scalability of the model.