An Efficient Parallel Triangle Enumeration on the MapReduce Framework

Hongyeon KIM  Jun-Ki MIN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.10   pp.1902-1915
Publication Date: 2019/10/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018EDP7421
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
triangle enumeration,  vertex partition,  graph data,  MapReduce,  

Full Text: PDF(1.3MB)>>
Buy this Article




Summary: 
A triangle enumerating problem is one of fundamental problems of graph data. Although several triangle enumerating algorithms based on MapReduce have been proposed, they still suffer from generating a lot of intermediate data. In this paper, we propose the efficient MapReduce algorithms to enumerate every triangle in the massive graph based on a vertex partition. Since a triangle is composed of an edge and a wedge, our algorithms check the existence of an edge connecting the end-nodes of each wedge. To generate every triangle from a graph in parallel, we first split a graph into several vertex partitions and group the edges and wedges in the graph for each pair of vertex partitions. Then, we form the triangles appearing in each group. Furthermore, to enhance the performance of our algorithm, we remove the duplicated wedges existing in several groups. Our experimental evaluation shows the performance of our proposed algorithm is better than that of the state-of-the-art algorithm in diverse environments.