## KLASTERISASI GRAF MENGGUNAKAN METODE MARKOV CLUSTER ALGORITHM (MCL)
Desti Riminarsih 1
Ilmiyati Sari 2
Feni Andriani 3
1,2,3 Fakultas Teknologi Industri, Universitas Gunadarma Jl. Margonda Raya No. 100, Depok 16424, Jawa Barat
1 destimath@staff.gunadarma.ac.id
2 ilmiyati@staff.gunadarma.ac.id
3 feni_andriani@staff.gunadarma.ac.id

## Abstrak
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.

## GRAPH CLUSTERING WITH MARKOV CLUSTER ALGORITHM (MCL) METHOD

## Abstract
Cluster analysis is one of the most widely used techniques for recognizing natural groups within an entity class. One method of cluster analysis in graph is the MCL method.  In  this  study,  the  MCL  algorithm  was  described  and  the  examples  of application in clustering graph. MCL is a flow simulation on a random walk until the discovery of the cluster. The algorithm begins by determining the representation of the graph in the form of an associated matrix. The next step is to determine the Markov  matrix  based  on  the  associated  matrix.  The  next  stage  is  the  expansion operation  on  the  Markov  matrix  followed  by  the  inflation  operation  on  the expansion  matrix.  The  next  step  is  to  check  whether  it  is  in  line  with  the convergence  criteria.  If  the  convergence  condition  has  not  been  reached  then  the process is repeated from the phase of expansion operation of the matrix.
Keywords:  Clustering, Graph, Inflation Operator, Markov Chain, Matrix, Random Walk.

## PENDAHULUAN
Data mining adalah  proses  untuk menemukan  informasi  yang  berguna secara  otomatis  di  repositori  data  yang besar.  Teknik  penambangan  data  di- kerahkan untuk menjelajahi database be- sar untuk menemukan pola baru dan ber- guna  yang  mungkin  tidak  diketahui  [1]. Salah satu teknik dalam data mining ada- lah analisis cluster yang merupakan studi matematis mengenai metode untuk mengenali  kelompok  alami  dalam  suatu kelas entitas [2]. Analisis cluster menge- lompokkan objek data hanya berdasarkan informasi  yang  terdapat  pada  data  yang menggambarkan  objek  dan  hubungan- nya.  Tujuannya  adalah  bahwa  objek  da- lam  suatu  kelompok  serupa  satu  sama lain dan berbeda dari objek dalam kelom- pok  lain.  Semakin  besar  kesamaan  (atau homogenitas) dalam suatu kelompok dan semakin  besar  perbedaan  antar  kelom- pok,  semakin  baik  atau  lebih  berbeda pengelompokannya.  Seluruh  koleksi clu- ster biasanya  disebut  sebagai clustering [1]. Analisis cluster memberikan  abs- traksi  dari  objek  data  individual  ke kelompok  tempat  objek  data  berada.  Se- lain  itu,  beberapa  teknik  pengelompokan mengkarakterisasi  setiap  cluster  dalam hal  prototipe  cluster  yang  berupa  objek data yang mewakili objek lain di cluster. Prototip  cluster  ini  dapat  digunakan  se- bagai  dasar  untuk  sejumlah  analisis  data atau teknik pengolahan data. Oleh karena itu,  dalam  konteks  utilitas,  analisis cluster  adalah  studi  teknik  untuk  mene- mukan prototip cluster yang paling repre- sentative terhadap data [1].
Aplikasi-aplikasi  dalam  analisis cluster  cukup  banyak  dan  telah  meng- hasilkan  banyak  metode  yang  mem- bingungkan [2].  Pada umumnya aplikasi klasik  memiliki  satu  kesamaan  yaitu adanya  anggapan  bahwa  entitas  diwakili oleh vektor, yang menggambarkan bagai-
mana  masing-masing  entitas  mendapat- kan  nilai  pada  serangkaian  karakteristik atau  fitur.  Perbedaan  antara  dua  entitas dihitung sebagai jarak antara masing-ma- sing  vektor  yang  menggambarkannya. Ketidaksamaan  dari  dua  vector  sesuai dengan  jarak  dalam  geometri  Euclidean yang sangat eksplisit [2].
Graf  adalah  objek  yang  memiliki sifat  kombinatorial  yang  jauh  lebih banyak yang tercermin pada beberapa is- tilah  seperti  simpul,  ruas  derajat  (jumlah tetangga),  jalur,  siklus,  keterhubungan, dan  sebagainya.  Bobot  ruas  biasanya tidak sesuai dengan jarak atau kedekatan yang  dapat  disematkan  dalam  geometri Euclidean,  juga  tidak  memerlukannya menyerupai  metrik  [2].  Beberapa  al- goritma clustering telah  dikembangkan salah satunya adalah algoritma clustering berbasis  graf  yang  terdiri  dari  4  macam yaitu MCODE, RNSC ( Restricted Neigh- borhood Search Clustering ), SPC ( Super Paramagnetic  Clustering )  dan  MCL ( Markov Clustering ) [3].
Analisis cluster berbasis  graf  erat kaitannya  dengan  bidang  partisi  graf, dimana  metode  ini  digunakan  untuk menemukan  partisi  optimal  dari  sebuah graf  dengan  batasan  tertentu.  Partisi didefinisikan secara ketat sebagai pemba- gian  beberapa  S  menjadi  himpunan  ba- gian  yang  memenuhi  asumsi  semua  pa- sang  himpunan  bagian  dipisahkan  dan penyatuan semua subset menghasilkan S.
Pada  partisi  graf,  ukuran  partisi yang  dibutuhkan  ditentukan  terlebih dahulu.  Tujuannya  adalah  untuk  memi- nimalkan  beberapa  fungsi  biaya  yang terkait  dengan  hubungan  yang  meng- hubungkan  elemen  partisi  yang  berbeda [2].  Hal  ini  merupakan  perbedaan  men- dasar  antara  graf  partisi  dan graph clustering  dimana  pada  graf clustering penemuan  kelompok-kelompok  dilaku- kan  secara  alami.  Pada  penelitian  ini
dijelaskan  metode  clustering  pada  graf menggunakan algoritma MCL.

## METODE PENELITIAN
Pada  bagian  ini  dijelaskan  tahapan klasterisasi  graf  dengan  menggunakan metode  MCL.  Konsep  utama  klasterisasi pada graf adalah simpul terhubung tinggi bisa berada dalam satu klaster sedangkan simpul  terhubung  rendah  bisa  berada dalam  kelompok  yang  berbeda  [2].
Jumlah  jalur  u-v  dengan  panjang  k  lebih besar  jika  u,  v  berada  pada  cluster  padat yang  sama,  dan  lebih  kecil  jika  berada pada kelompok yang berbeda. Suatu ran- dom  walk pada  graf  akan  meninggalkan klaster  sampai  simpul-simpulnya  telah dikunjungi.

## Random Walk
Random walk pada graf terdiri dari urutan  simpul  yang  dihasilkan  dari simpul  awal  dengan  memilih  ruas,  me- lewati  ruas  menuju  simpul  baru  dan mengulangi  prosesnya [4]. Random walk bisa  dimulai  dari  simpul  manapun.
Dimulai pada simpul r, jika random walk akan  mencapai  simpul  t  dengan  pro- babilitas  tinggi,  maka  r  dan  t  harus  di- kelompokkan  bersama.  Berdasarkan  se- buah  graf,  terdapat  banyak  tautan  dalam sebuah  klaster  dan  lebih  sedikit  hu- bungan  antar  klaster.  Jika  dimulai  dari sebuah simpul, dan kemudian melakukan random  walk ke  simpul  yang  terhubung, kemungkinan  lebih  cenderung  untuk tinggal  di  dalam  sebuah  klaster  daripada melakukan walk di antara keduanya. Hal ini merupakan dasar dari algoritma MCL. Random walk pada graf dapat digunakan untuk  menentukan  keberadaan  suatu kelompok yang ditandai dengan kecende- rungan berkumpulnya suatu aliran. Random  walk pada  graf  dihitung  dengan menggunakan " Markov Chains "[5].

## Markov Chain
Markov  Chain merupakan  suatu
barisan variable x 1 , x 2 , x 3 dan seterusnya dimana diberikan stata saat ini, stata yang sebelumnya  dan  stata  berikutnya  yang bersifat  independen.  Probabilitas  untuk langkah  waktu  berikutnya  hanya  bergan- tung  pada  probabilitas  saat  ini. Random walk merupakan  suatu  contoh Markov Chain dengan  menggunakan  matriks transisi probabilitas [5].

## Operator Inflasi
Definisi 1. Diberikan matriks M ϵ R Rx1 , M ≥0, bilangan real nonnegative r, matriks hasil pengskalaan  kembali  setiap  kolom  M dengan koefisien pangkat r disebut r M 
, dan r  disebut  operator inflasi  dengan koefisien  pangkat  r.  Secara  formal,
1 1 : Rx Rx r R R   didefinisikan dengan
      1 / r r k r pq iq pq i M M M     (1)
Jika  subscript  dihilangkan  maka  pada persamaan (1) nilai koefisien pangkat (r) adalah 2.

## MCL
Pada  metode  MCL  simulasi  aliran pada  random  walk  merupakan  konsep inti  hingga  ditemukannya  klaster.  Aliran lebih  mudah  berada  di  dalam  wilayah padat  daripada  di  batas  yang  jarang, namun  dalam  jangka  panjang  efek  ini akan  lenyap.  Selama  kekuatan  sebelum- nya  dari  Markov  Chain,  bobot  ruas akan lebih tinggi pada mata rantai yang berada di  dalam  cluster,  dan  lebih  rendah  di antara  kelompok-kelompok.  Hal  ini  ber- arti  terdapat  korespondensi  antara  distri- busi  bobot  di  seluruh  kolom  dan cluste- ring . MCL dengan sengaja meningkatkan pengaruh  dengan  cara  menghentikan sebagian dalam Markov Chain kemudian menyesuaikan  transisi  menurut  kolom. Untuk  setiap  simpul  pada  graf,  nilai transisi  diubah  sehingga  mengakibatkan tetangga yang kuat diperkuat lebih lanjut sedangkan tetangga yang kurang populer diturunkan.  Penyesuaian  ini  bisa  dila-
kukan dengan mengangkat satu kolom ke kekuatan  non-negatif,  dan  kemudian kembali normal [5].

## Algoritma MCL
Markov Clustering Algorithm (MCL)  adalah  algoritma  cluster  yang
cepat  untuk  graf  yang  didasarkan  pada simulasi  aliran  ( flows )  pada  graf.  MCL dapat  pula  dilakukan  pada  graf  yang terboboti.
Tahapan dalam melakukan klasteri- sasi graf disajikan pada Gambar 1.
Gambar 1. Tahapan Algoritma MCL
Berdasarkan  Gambar  1,  penjelasan tahapan  algoritma  MCL  [6,  7]  sebagai berikut:
1. input graf  yang  akan  diklaste- risasi, nilai parameter power yaitu e,  nilai parameter  inflasi  yaitu r dan nilai toleransi error .
2. Buatlah associated  matrix ( G M ) yang  bersesuaian  dengan  graf pada langkah 1.
Associated  matrix disebut  juga dengan  matriks  adjasensi  yaitu matriks  yang  kolom  dan  barisnya merepresentasikan  simpul  pada graf,  misalnya  baris  dan  kolom  1 merepsentasikan  simpul  1,  se-
dangkan  busurnya  direpresentasi- kan oleh entri-entri pada associa- ted  matrix tersebut,  dimana  sim- pul-simpul  yang  dihubungkan dengan  sebuah  busur  diberi  entri 1  dan  yang  tidak  berhubungan diberi entri 0.
3. Tambahkan loop pada  setiap simpul  atau  dengan  kata  lain associated matrix yang  diperoleh pada  langkah  2  ditambahkan dengan matriks identitas n I .
4. Normalisasi  matriks  hasil  pada langkah  3.  Pada  langkah  ini, setiap entri matriks dibagi dengan jumlah  entri  matriks  di  kolom
tersebut  sehingga  diperoleh  ma- triks  dengan  jumlah  entri  dari setiap kolom adalah 1.
5. Pada  tahap  ini  dilakukan  operasi ekspansi  matriks  yang  dilakukan dengan  memangkatkan    matriks yang  diperoleh  pada  langkah  4 dengan pangkat e, dalam hal ini e = 2 .
6.  Pada  tahap  ini  dilakukan  operasi inflasi matriks hasil proses ekpan- si  (matriks  yang  diperoleh  pada langkah  5)  dengan  parameter inflasi r.
7. Suatu matriks hasil dari langkah 6 disebut  konvergen  jika  nilai residual  energy  lebih  kecil  dari- pada  toleransi error maka  proses berhenti  dan  diperoleh  matriks yang  menunjukkan  klasterisasi. Jika  kondisi  tersebut  belum  di- capai  maka  ulangi  kembali  lang- kah  5  dan  6  hingga  diperoleh kondisi konvergen.
8. Interpretasikan matriks pada lang- kah 7 sehingga ditemukan cluster-cluster dari graf.

## HASIL DAN PEMBAHASAN
Pada bagian ini dijelaskan implementasi  metode  MCL  pada  graf berikut:
Gambar 2. Graf
Langkah  pertama  adalah  membaca graf, menentukan parameter ekspansi (p), parameter  inflasi  (r),  dan  toleransi error (e).  Graf  yang  diklasterisasi  adalah  graf
yang  ditunjukkan  pada  Gambar  2.  Nilai parameter yang diambil adalah p = 2, r = 2, dan e = 0.001.
Berdasarkan pada Gambar 2, associated matrix ( G M ) adalah
𝑀 𝐺 = [ 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0
0 1 0 0 0 1 1 0 ] Langkah selanjutnya adalah menambahkan loop pada  graf  dengan cara  menambahkan  nilai  1  pada  setiap entri diagonal dari 𝑀 𝐺 sehingga diperoleh matriks berikut:
[ 1 1 0 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 1 0 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1
1 1 ]
Pada  proses  normalisasi  matriks terlebih  dahulu  ditentukan  jumlah  tiap kolom.  Misal  pada  kolom  1  dari  matriks diatas,
[ 1 1 0 0 0 1 1 0 0 0] Jumlah  kolom  1  =  4,  sehingga  hasil normalisasi kolom 1 adalah
1 4 × [ 1 1 0 0 0 1 1 0 0 0] = [ [ 0.25 0.25 0 0 0 0.25 0.25 0 0 0 ] ]
Sehingga matriks hasil proses normalisa-
si tertera pada gambar 3.
Gambar 3. Hasil Poses Normalisasi
Langkah  berikutnya  adalah  mela- kukan  operasi  ekspansi  matriks.  Matriks hasil  normalisasi  diekspansi  dengan  cara
dipangkatkan  2,  sehingga  diperoleh  hasil seperti pada gambar 4.
Gambar 4. Hasil operasi Ekspansi Matriks
Langkah  selanjutnya  adalah  di- lakukan  operasi  inflasi  matriks  hasil proses ekpansi dengan parameter inflasi r
=  2.  Gambar  5  adalah  matriks  hasil operasi inflasi.
Gambar 5.  Matriks hasil operasi inflasi.
Selanjutnya  menentukan  apakah matriks hasil operasi inflasi sudah meme- nuhi kriteria konvergen. Pada iterasi per- tama  ini  diperoleh  nilai  residual  energi: 0.162050  sehingga  proses  diulangi  lagi
dari tahap 5 hingga diperoleh kondisi sta- bil.
Berdasarkan  Tabel  1  nilai  residual energi  mulai  menurun    pada  iterasi  ke-3 hingga  ke-9.  Pada  iterasi  ke-9  nilai
residual  energi  <  0.001  sehingga  iterasi berhenti  pada  iterasi  ke-9  merupakan matriks  yang  menunjukkan  klaster- klaster dari graf.
Tabel 1. Residual Energi Iterasi ke-i Residual energi 1 0.162050 2 0.156611 3 0.161669 4 0.137281 Iterasi ke-i Residual energi 5 0.127801 6 0.124785 7 0.085941 8 0.014665 9 0.000000
Klasterisasi berhasil ditentukan dengan  banyak  iterasi  sebanyak  9. Gambar  6  adalah  matriks  hasil  operasi inflasi dari iterasi ke-2 hingga ke-9.
Gambar 6. Matriks Hasil Operasi Inflasi dari Iterasi ke-2 Hingga ke-9
Matriks  pada  iterasi  ke-9  merupa- kan  matriks  yang  menunjukkan  hasil klasterisasi  graf.  Klaster  ditandai  dengan baris  yang  memiliki  entri  tak  nol.  Entri matriks  yang  bernilai  1  pada  baris  yang sama  menunjukkan  bahwa  entri-entri tersebut berada dalam klaster yang sama. Kolom matriks menunjukkan simpul graf.
Pada  matriks  hasil  iterasi  ke-9  di- peroleh  bahwa  pada  baris  pertama,  entri yang  bernilai  1  ada  di  kolom  ke-1,  ke-6,
dan  ke-7.  Pada  baris  ke-4  diperoleh bahwa entri yang bernilai 1 ada di kolom ke-4,  ke-8,  ke-9,  dan  ke-10.  Pada  baris ke-5  diperoleh  bahwa  entri  yang  bernilai 1 ada di kolom ke-2, ke-3, dan ke-5. Kolom  pada  matriks  merepre- sentasikan simpul pada graf. Berdasarkan matriks  hasil  iterasi  ke-9  maka  dapat disimpulkan  bahwa  simpul-simpul  pada graf  dikelompokkan  ke  dalam  3  klaster. Ketiga  klaster  tersebut  adalah  (1,6,7),
(4,8,9,10)  dan  (2,3,5).  Klaster  (1,6,7) dengan  simpul  1  sebagai  pusatnya, klaster  {4,  8,  9,  10}  dengan  simpul  4 sebagai  pusatnya,  dan  klaster  {2,  3,  5} dengan  simpul  5  sebagai  pusatnya.

## Gambar 3. Graf Hasil MCL
Berdasarkan  pada  Gambar  3  dapat dilihat  hasil  klasterisasi  metode  MCL yaitu  graf  memiliki  3  klaster  yang  ber- beda.

## SIMPULAN DAN SARAN
Algoritma  MCL  merupakan  algo- ritma  yang  mudah  untuk  diterapkan  dan memiliki  konsep  sederhana  dengan  dua operasi utama yaitu operasi ekspansi dan operasi  inflasi.  Penentuan  klaster  ber- dasarkan  algoritma  ini  dilakukan  secara alami.  Setiap  permasalahan  yang  dapat direpresentasikan dalam sebuah graf ma- ka  proses  klasterisasinya  dapat  menggu- nakan algoritma MCL.

## DAFTAR PUSTAKA
[1] [Van Dongen, 2000] Van Dongen, S. 2000.  Graph  Clustering  by  Flow
Simulation. PhD  Thesis .  University of Utrecht, The Netherlands.
[2] [Tan,  Steinbach,  dan  Kumar,  2006] Tan,  P.  N.,  Steinbach,  M.,  dan Kumar,  V.  2006.  Introduction  to
Data Mining . Boston: Pearson Education. [3] [Brohee  dan  van  Helden,  2006] Brohee,  S.  dan  van  Helden,  J.  2006. Evaluation  of  Clustering  Algorithms For Protein-Protein Interaction Networks. BMC Bioinformatics , Vol. 7, pp. 488.
[4] [Blum, Hopcroft, dan Kannan, 2015] Blum, A., Hopcroft, J., dan Kannan, R.  2015. Foundations  of  Data Science. Retrieved from https://www.cs.cornell.edu/jeh/book May2015.pdf.
[5] [Macropol,  2009]  Macropol,  K. 2009.  Clustering  on  Graphs:  The Markov  Cluster  Algorithm  (MCL).
Retrieved from https://www.cs.ucsb.edu/%7Exyan/c lasses/CS595D2009winter/MCL_Pre sentation2.pdf.
[6] [Stijn  van  Dongen]  Stijn  van Dongen,  MCL  -  a  cluster  algorithm for graphs. Retrieved from http://www.micans.org/mcl/.
[7] [Enright,  van  Dongen,  Ouzounis, 2002] Enright, A. J., van Dongen, S., dan  Ouzounis,  C.  A.  2002.  An Efficient  Algorithm  for  Large-scale Detection  of    Protein  Families. Nucleic  Acids  Research ,  Vol.  30, No. 7, pp. 1575 – 1584.