Perpustakaan Digital ITB

Graf sering digunakan sebagai model di berbagai bidang, sejalan dengan hal tersebut model graf yang dihasilkan beraneka ragam, mulai dari yang sederhana seperti graf yang memodelkan pertemanan di aplikasi sosial media yang dikenal dengan graf homogen, sampai pada graf heterogen yang kompleks seperti graf yang memodelkan kasus bioinformatika. Pengolahan graf yang kompleks khususnya deteksi komunitas atau pembentukan cluster masih bersifat statis yaitu pengolahan untuk satu graf yang utuh. Adapun pengolahan sekumpulan graf dengan evolutionary clustering masih terbatas pada graf homogen, dan graf heterogen dengan skema tertentu. Belum ada algoritma evolutionary clustering yang menangani graf heterogen kompleks. Berdasarkan penjelasan tersebut, Tesis ini akan membahas mengenai pengembangan metode evolutionary clustering untuk graf heterogen kompleks temporal. Algoritma GPNRankClus dan ENetClus diadopsi sebagai algoritma untuk proses cluster setiap snapshot graf kompleks dan evolutionary clustering. Dengan melakukan analisis terhadap algoritma evolutionary clustering, mempelajari setiap tahap pada algoritma tersebut dan melakukan analisis terhadap algoritma evolutionary clustering, dan selanjutnya mengembangkan algoritma evolutionary clustering untuk graf heterogen kompleks. Pengembangan dilakukan dengan menambah beberapa tahap pada algoritma clustering graf GPNRankClus berdasarkan pada algoritma evolutionary clustering ENetClus. Tahapan yang ditambahkan tersebut menerima input dari hasil clustering dari snapshot sebelumnya yaitu nilai parameter-parameter distribusi gamma dan poisson dan variable bantu, selain itu skor rangking sebelumnya ditambahkan pada skor rangking yang didapat dengan bobot tertentu. Eksperimen dilakukan dengan beberapa graf temporal. Hasil pengujian menunjukkan algoritma evolutionary clustering untuk graf heterogen kompleks memberikan hasil clustering yang konsisten antar snapshot. Bobot untuk skor rangking berpengaruh terhadap konsistensi antar snapshot dan kualitas hasil clustering. Berdasarkan penelitian yang dilakukan dapat disimpulkan bahwa untuk melakukan evolutionary clustering pada graf heterogen kompleks dapat dilakukan dengam mengembangkan algoritma clustering graf yang menangani graf heterogen kompleks, dengan menambahkan tahapan yang menerima input dari hasil sebelumnya sehingga memberikan hasil clustering yang konsisten.