VERTEX-CUT PARTITIONING PERFORMANCE ANALYSIS FOR FASTCD ALGORITHM IN LARGE-SCALE GRAPH

• Main Author: RUSDIWIJAYA - NIM: 23515060 , RIZKI
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/30596
• Institution: Institut Teknologi Bandung

<p align="justify">Rapid processing of large-scale graphs has become a popular research topic on domains such as graph partitioning and community detection. This research discusses the performance of vertex-cut partitioning for the processing of community detection on large-scale graphs. Fast Community Detection (FastCD) algorithm is community detection algorithm based on modularity optimization capable of performing community detection on large-scale graphs. Community detection on large-scale graphs requires graph partitioning techniques that partition large-scale graphs into several subgraphs for processing to be performed in parallel, so that computational loads can be distributed across machines in the computer cluster. In contrast to conventional parallel data processing, community detection processing on FastCD algorithm requires neighboring edge and vertex information when calculating the modularity value of the partition on each vertex. <br /> <br /> <br /> The research was conducted on graph parallel distributed framework, GraphX, which is a graph processing component in Spark. The vertex-cut partitioning strategy includes RandomVertexCut, CanonicalRandomVertexCut, EdgePartition1D, and EdgePartition2D applied to FastCD algorithm for community detection on large-scale graphs in parallel. <br /> <br /> <br /> Based on experimental results, the performance of each vertex-cut partitioning strategy for the FastCD algorithm performs community detection depending on the condition of the graph. The performance of the vertex-cut partitioning strategy on the FastCD algorithm can be measured by community detection processing times, community detection rates, and the quality of community detection results. EdgePartition1D strategy has the best performance for FastCD algorithm performs in parallel community detection on large-scale graphs with the number of edges reaching 7.600.595 and the number of vertices reaching 685.230. <p align="justify">