PENENTUAN STRUKTUR KOMUNITAS DI DALAM JARINGAN SOSIAL MENGGUNAKAN DIFFERENTIAL EVOLUTION

TAUFAN BAGUS DWI P A, Dr. Azhari, MT.

2020 | Tesis | MAGISTER ILMU KOMPUTER

Penelitian mengenai menentukan struktur komunitas dalam jaringan yang kompleks telah menarik banyak perhatian diberbagai aplikasi, seperti jaringan e- mail, jaringan sitasi, jaringan sosial, jaringan metabolisme, jaringan maskapai penerbangan, jaringan biologis, jaringan informasi, jaringan teknologi, dan jaringan komputer. Kepopuleran menentukan struktur komunitas disebabkan karena dapat menganalisis struktur, dan fungsional sebuah jaringan, yang mana jaringan atau komunitas itu sendiri dapat diartikan sebagai suatu node yang terkait erat didalam suatu jaringan informasi. Sedangkan, untuk menentukan struktur komunitas dengan memaksimalkan nilai modularitas adalah hal yang sulit. Oleh karena itu, banyak penelitian memperkenalkan algoritma-algoritma baru untuk memecahkan masalah dalam menentukan struktur komunitas dan memaksimalkan nilai modularitas tersebut. Differential Evolution adalah sebuah algoritma berbasis evolusi yang mirip dengan algoritma genetika (GA) yang mana DE sangat sederhana dan efisien. DE dapat memberikan solusi kecepatan dan ketepatan, yang sangat cocok untuk pendeteksian sebuah komunitas. DE tidak perlu mengetahui tentang struktur komunitas dan jumlah komunitas untuk dapat mendeteksi sebuah komunitas. Pada penelitian ini berfokus pada Differential Evolution based Community Detection (DECD) yang ditambahkan fitur clean up didalamnya. Hasil akhir penelitian ini merupakan hasil perbandingan nilai modularitas berdasarkan penentuan struktur komunitas dari DECD, Algoritma Girvan and Newman dan Algoritma Louvain. Hasil nilai modularitas terbaik diperoleh dengan menggunakan DECD yang mendapatkan hasil 0,6833 untuk dataset Zachary karate club, 0,7446 untuk dataset Bootlenose dolphins, 0,7242 untuk dataset American college football, dan 0,5892 untuk dataset Books about US politics.

Research on determining community structure in complex networks has attracted a lot of attention in various applications, such as e-mail networks, citation networks, social networks, metabolic networks, airline networks, biological networks, information networks, technology networks, and computer networks. The popularity of determining the community structure is because it can analyze the structure and functionality of a network, where the network or community itself can be interpreted as a node that is closely related in an information network. Meanwhile, it is difficult to determine a community structure by maximizing the value of modularity. Therefore, many studies have introduced new algorithms to solve problems in determining community structure and maximizing the value of this modularity. Differential Evolution is an evolution-based algorithm that is similar to the genetic algorithm (GA) in which DE is very simple and efficient. DE can provide speed and accuracy solutions, which are very suitable for detection of a community. DE does not need to know about community structure and number of communities to be able to detect a community. This research focuses on Differential Evolution based Community Detection (DECD) which adds a clean up feature in it. The final result of this research is the comparison of the modularity value based on the community structure determination from DECD, Girvan and Newman Algorithm and Louvain Algorithm. The best results for modularity were obtained using DECD which got 0.6833 for the Zachary's karate club dataset, 0.7446 for the Bootlenose dolphins dataset, 0.7242 for the American college football dataset, and 0.5892 for the Books about US politics dataset.

Kata Kunci : Community detection, differential evolution, social networks, community structure, modularity