COMPARISON OF GIRVAN-NEWMAN AND LOUVAIN COMMUNITY DETECTION ON GRAPH CLUSTERING ALGORITHM FOR RECOMMENDATION SYSTEM

• Main Author: Alifia Mahardika, Ilma
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/49639
• Institution: Institut Teknologi Bandung

One way to achieve scalability in recommendation system is by applying graph clustering strategy. At present, there is SCLUB-CD Algorithm (Yang & Toni, 2019) which handles this. SCLUB-CD Algorithm utilizes the Louvain Algorithm as a community detection. On the other hand, there is a study which shows that Girvan-Newman algorithm with MC Modularity calculation (GN-MC) gives high accuracy of 99.15% (Mairisha & Saptawati, 2016). This situation brings up an opportunity to improve the performance of SCLUB-CD Algorithm by replacing the community detection that it used. This work conducted an experiment to compare Louvain Algorithm with GN-MC Algorithm on the implementation of SCLUB-CD Algorithm. Experiments were carried out on the Last.FM and Bukalapak dataset. Cluster quality test and experiments with variations in data components were also carried out to support the result analysis for main experiments. The result obtained is the implementation of SCLUB-CD Algorithm using GN-MC Algorithm can provide better results than Louvain Algorithm. This can be seen from lower cumulative regret value. The difference in cumulative regret can reach an average difference of 92.0709 and a maximum difference of 191. This can occur due to differences in the clustering strategies of the two community detections. In addition, the use of the GN-MC Algorithm has new consequences in term of very long running time. GN-MC Algorithm has a bottleneck in the MC Modularity calculation process. For more than 10,000 users, Louvain Algorithm is better because this algorithm still runs in seconds, while GN-MC Algorithm has limitation only able to process less than 10,000 users.