An Efficient Parallel Triangle Enumeration on the MapReduce Framework
Open Access
- 1 October 2019
- journal article
- research article
- Published by Institute of Electronics, Information and Communications Engineers (IEICE) in IEICE Transactions on Information and Systems
- Vol. E102.D (10) , 1902-1915
Abstract
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.Keywords
This publication has 20 references indexed in Scilit:
- PTE2016
- Parallel Triangle Counting and Enumeration Using Matrix Algebra2015
- An efficient MapReduce algorithm for counting triangles in a very large graph2013
- Massive graph triangulation2013
- What is Twitter, a social network or a news media?2010
- Graph Twiddling in a MapReduce WorldComputing in Science & Engineering, 2009
- MapReduceCommunications of the ACM, 2008
- Community structure in social and biological networksProceedings of the National Academy of Sciences, 2002
- Graph structure in the WebComputer Networks, 2000
- Join processing in relational databasesACM Computing Surveys, 1992