KLASTERISASI GRAF MENGGUNAKAN METODE MARKOV CLUSTER ALGORITHM (MCL)

Abstract

Analisis klaster merupakan salah satu teknik yang banyak digunakan untuk mengenali kelompok alami dalam suatu kelas entitas. Salah satu metode analisis klaster pada graf adalah metode MCL. Pada penelitian ini dijelaskan algoritma MCL dan contoh penerapan pada klasterisasi graf. MCL merupakan suatu simulasi aliran pada random walk hingga ditemukannya klaster. Algoritma diawali dengan menentukan representasi graf dalam bentuk associated matrix. Langkah berikutnya adalah menentukan matriks Markov berdasarkan pada associated matrix. Tahap berikutnya adalah operasi ekspansi pada matriks Markov yang dilanjutkan dengan operasi inflasi pada matriks hasil ekspansi. Langkah berikutnya adalah mengecek apakah sudah sesuai dengan kriteria konvergensi. Jika kondisi konvergensi belum tercapai maka proses diulang kembali dari tahap operasi ekspansi matriks.

Kata Kunci:   Graf, Klasterisasi, Markov Chain, Matriks, Operator Inflasi, Random Walk.