An Efficient Triangle Enumeration on Parallel and Distributed Frameworks

摘要

Triangle enumerating problem is one of fundamental problems of graph data. Although several triangle enumerating algorithms based on MapReduce which is a distributed parallel framework have been proposed, they still suffer from generating a lot of intermediate data. In this paper, we propose an efficient algorithm to enumerate every triangle in massive graph. A wedge consists of a cone vertex and two end-nodes having one pass through the cone vertex. Since a triangle is composed of one edge and one wedge, our algorithm checks the existence of an edge that is incident to two end-nodes in each wedge. We partition vertex set into several partial vertex sets to prevent generating numerous wedges. Our experimental evaluation shows the performance of proposed algorithm is better than competitors.