TRIANGLE COUNTING USING HDRF GRAPH PARTITION STRATEGY IN APACHE SPARK GRAPHX

• Main Author: Novanto, Dicky
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/43524
• Institution: Institut Teknologi Bandung

Triangle counting algorithm is one of graph algorithm that can be used to analyze a graph dataset. The graph that will be analyzed sometimes needs to be partitioned first into several nodes in a cluster of graph processing engine before applying a graph algorithm to the graph. Graph partition algorithm can affect performance of a distributed graph algorithm and in this research, HDRF graph partitition strategy is implemented and processing it in Apache Spark GraphX. HDRF algorithm is a graph partition algorithm that can result low replication factor value so that it can minimize the number of communications needed between nodes in a cluster when executing a graph algorithm. In this research, it is done also experiment on triangle counting algorithm on a partitioned graph using HDRF and Random Vertex Cut algorithm on Apache Spark GraphX. The purpose of the experiment is execution time comparison between executing triangle counting algorithm with graph partitioned using HDRF and Random Vertex Cut algorithm in Apache Spark GraphX and then analyzing the time comparison. Based on the experiment, it shows that execution time of triangle counting algorithm on graph partitioned using HDRF is better than using graph partitioned with Random Vertex Cut in a big dataset, Autonomous Systems by Skitter, with improvement of 20.79%.