Page 104 - Science and Technology For Society 5.0

~ Science and Technology for Society 5.0 ~ 67

6. Markov Clustering (MCL)
Berdasarkan Dongen (2000), terdapat tiga proses utama yang menjadi
jantung dari algortima MCL, yaitu ekspansi (expand), inflasi (inflation), dan
pemotongan (prune). Berikut merupakan penjelasan dari setiap proses pada
MCL.
a. Expand
Expand mensimulasikan random walk (flow) pada graf G. Input berupa
matriks Markov M yang sesuai dengan graf G dan output berupa matriks
Mexp dimana Mexp = Expand(M) = M p ,p + adalah parameter ekspansi. M
p
merupakan matriks adjacency dari graf G, sehingga bentuk M menyatakan
probabilitas transisi dari sebuah node pada G ke node lainnya yang berjarak
p dari node tersebut.

b. Inflate
Inflate memperkuat flow yang kuat, memperlemah flow yang lemah.
Jika diberikan matriks M R mxn , M  0, r  ,r  , maka operator inflasi
0
Γ r : mxn didefinisikan sebagai:
( ) r
M
)
( Γ M = m ij r , i = 1 m j , = 1 n (3)
 k= 1 ( )
r
ij
M
kj
Nilai antara 0 dan 1 akan meningkatkan kehomogenan (keseragaman)
dari matriks M, sedangkan nilai r antara 1 dan ∞ akan meningkatkan
ketakseragaman dari M, dimana entri dengan nilai yang kecil akan semakin
diperkecil dan entri dengan nilai yang besar akan semakin diperbesar. Nilai
r yang negatif tidak digunakan sebab akan mengubah urutan dari entri-entri
pada M, dimana entri bernilai kecil akan menjadi besar, dan sebaliknya. Hal
ini akan berakibat pada rusaknya topologi graf, dimana daerah-daerah yang
seharusnya padat dan memiliki satu atau lebih pusat cluster akan diubah
menjadi daerah dengan densitas yang rendah.

c. Prune
Prune adalah penghapusan entri dari M dengan nilai yang dianggap
cukup kecil pada setiap kolom, yaitu entri yang nilainya kurang dari minval,
−
5
dimana default minval adalah 10 . Dengan melakukan proses prune,
hubungan antar-node dengan busur yang memiliki probabilitas yang rendah