Perpustakaan Digital ITB

Dalam konteks klasterisasi berbasis graf, tahap awal algoritma berperan penting karena dapat menentukan arah pembentukan klaster. Penentuan jumlah klaster menjadi aspek penting karena dapat memiliki konsekuensi rekayasa ketika hasil klasterisasi digunakan sebagai dasar pengambilan keputusan. Penelitian ini memanfaatkan graph coloring (pewarnaan graf) sebagai strategi inisialisasi untuk mengurangi ketergantungan algoritma klasterisasi terhadap penentuan jumlah klaster secara manual. Beragam variasi graph coloring, seperti greedy, balanced, dan distance coloring, diterapkan ke dalam beberapa algoritma klasterisasi, seperti k-algo, pagerank, dan spectral clustering, untuk mengevaluasi pengaruh metode graph coloring sebagai inisialisasi terhadap kualitas hasil klasterisasi dan efisiensi algoritma. Eksperimen dilakukan menggunakan data sintetis dan data publik yang diperoleh dari SNAP, NetworkX, dan Network Repository. Evaluasi dilakukan menggunakan metrik conductance, modularitas, Adjusted Rand Index (ARI), dan Normalized Mutual Information (NMI). Hasil eksperimen menunjukkan bahwa, pada graf kecil hingga sedang, metode inisialisasi berbasis graph coloring mampu memperkirakan jumlah klaster dengan cukup baik serta mempertahankan kualitas dan efisiensi klasterisasi. Selain itu, algoritma klasterisasi yang memanfaatkan graph coloring mampu menghasilkan klasterisasi yang kompetitif dibandingkan algoritma klasterisasi tradisional seperti Louvain dan spectral clustering. Namun, performa metode inisialisasi berbasis graph coloring belum dapat disimpulkan unggul pada setiap jenis graf. Secara keseluruhan, hasil eksperimen menunjukkan potensi graph coloring sebagai strategi inisialisasi algoritma klasterisasi untuk mengurangi ketergantungan penentuan jumlah klaster secara manual.