Deteksi Komunitas pada Graph Berbobot dengan Paralelisasi Metode Girvan-Newman Termodifikasi

Neny Sulistianingsih, Drs. Edi Winarko, M.Sc., Ph.D; Anny Kartika Sari, S.Si., M.Sc., Ph.D

2023 | Disertasi | S3 Ilmu Komputer

Metode Girvan-Newman merupakan salah satu metode tonggak di bidang deteksi komunitas. Banyaknya kelebihan dari metode Girvan-Newman menyebabkan banyak peneliti menggunakan metode ini untuk melakukan deteksi komunitas pada data berupa graph. Namun seperti metode-metode lainnya, metode Girvan-Newman memiliki beberapa kekurangan. Kelemahan-kelemahan tesebut antara lain lambatnya waktu pemrosesan dan metode Girvan-Newman yang hanya dapat memproses graph berbobot positif saja.

Berdasarkan beberapa hal tersebut, pada penelitian ini dilakukan pengembangan terhadap metode Girvan-Newman dengan modifikasi terhadap metode pencarian jalur terpendek metode Johnson sehingga graph berbobot positif dan negatif dapat diproses Kemudian, pada metode Girvan-Newman termodifikasi, perhitungan pair dependencies juga dilakukan bersamaan dengan perhitungan edge betweenness dengan tujuan untuk mempertahankan kualitas komunitas yang dihasilkan. Selanjutnya, dari metode Girvan-Newman termodifikasi digunakan konsep multiprocessing untuk mempercepat waktu pemrosesan. 

Pengujian dilakukan terhadap metode Girvan-Newman termodifikasi dan paralelisasi terhadap metode Girvan-Newman termodifikasi dengan mengukur waktu pemrosesan, modularitas dan NMI. Metode pembanding yang digunakan adalah metode Girvan-Newman dan paralelisasi dari Metode Girvan-Newman. Jumlah unit pemrosesan yang digunakan adalah 2, 4, 8 dan 16. Hasil pengujian menunjukkan bahwa metode Girvan-Newman termodifikasi dengan persentase selisih modularitas berkisar dari -1,73% hingga 12,31?n -7,24% hingga 0,59% untuk graph berbobot positif dan berbobot positif dan negatif, berturut-turut. Selanjutnya, hasil pengujian terkait waktu pemrosesan menunjukkan bahwa paralelisasi dari Metode Girvan-Newman termodifikasi mampu mempercepat waktu pemrosesan yaitu rata-rata sebesar 0,892 kali dengan kisaran 0,732 hingga 0,962 kali untuk graph berbobot positif dan rata-rata sebesar 1,413 dengan kisaran 0,498 hingga 3,794 kali untuk graph berbobot positif dan berbobot positif dan negatif dari waktu pemrosesan yang dihasilkan paralelisasi dari Metode Girvan-Newman. Selanjutnya, pengujian menggunakan NMI menunjukkan bahwa rata-rata kemiripan hasil komunitas dari metode Girvan-Newman termodifikasi adalah sebesar 0,670 dan 0,472 sedangkan untuk paralelisasi terhadap metode Girvan-Newman termodifikasi adalah sebesar 0,699 dan 0,621 untuk graph berbobot positif dan berbobot positif dan negatif, berturut-turut.

The Girvan-Newman method is one of the milestone methods in community detection. The many advantages of the Girvan-Newman method have caused many researchers to use this method to detect communities in data in graphs. But like other methods, the Girvan-Newman method has some drawbacks. These weaknesses include slow processing time and the Girvan-Newman method, which can only process graphs with positive weights.

Based on some of these things, this research carried out the development of the Girvan-Newman method by modifying the Johnson method to find the shortest path so that the graphs with positive weights and negative weights can be processed. Then, in the modified Girvan-Newman method, pair dependencies calculations are performed simultaneously with edge betweenness calculations to maintain the quality of the resulting community. Furthermore, multiprocessing speeds up processing time from the modified Girvan-Newman method.

Tests were carried out on the modified Girvan-Newman method and parallelization on the modified Girvan-Newman method by measuring processing time, modularity, and NMI. The comparison method used is the Girvan-Newman method and the parallelization of the Girvan-Newman method. The number of processing units used was 2, 4, 8, and 16. The test results showed that the Girvan-Newman method was modified with a percentage difference in modularity ranging from -1,73% to 12,31% and -7,24% to 0,59% for graphs with positive weights and positive and negative weights, respectively. Furthermore, the test results related to processing time show that the parallelization of the modified Girvan-Newman Method can speed up processing time, namely an average of 0,892 times with a range of 0,732 to 0,962 times for positive weighted graphs and an average of 1,413 with a range of 0,498 to 3,794 times for graph is positively weighted and positively and negatively weighted from the processing time resulting from the parallelization of the Girvan-Newman method. Furthermore, testing using NMI showed that the average similarity of community results from the modified Girvan-Newman method was 0,670 and 0,472, while for parallelizing the modified Girvan-Newman method, it was 0,699 and 0,621 for positive weighted and positive and negative weighted graphs, respectively.

Kata Kunci : deteksi komunitas, graph berbobot, metode Girvan-Newman, paralelisasi, pair dependencies