Memahami Metode Centrality Dasar


Materi kelas Text dan Web Mining hari ini mendiskusikan tentang 3 metode penghitungan untuk mendapatkan bobot centrality dari setiap node yang ada dalam sebuah graf. Perhitungan centrality dalam suatu undirected graph dapat menghasilkan suatu bobot yang menentukan node mana yang paling penting dalam graf tersebut. Dalam aplikasi web, kita dapat mengasumsikan bahwa setiap node dalam graf mewakili sebuah laman, sedangkan busur (edge) yang terbentuk antar dua node mewakili ada atau tidaknya tautan. Dalam konteks di kelas, saya hanya menekankan tentang penerapan perhitungan centrality untuk suatu graf yang tidak berarah, artinya tidak dibedakan antara out-links ataupun in-links.

Setidaknya terdapat 3 buah metode dasar untuk dapat menghitung bobot centrality dari setiap node dalam suatu graf, yaitu: degree, closeness, dan betweenness. Degree Centrality akan menghitung bobot suatu node ke i (diberi notasi CD(i)) berdasar banyaknya edge yang terbentuk antara node i dengan node yang lainnya. Rumus sederhana untuk penghitungan bobot suatu node dapat digunakan bentuk normalisasi sebagai berikut :

degree_centralitySebagai contoh sederhana diberikan sebuah graf sebagai berikut (untuk penggambaran graf saya menggunakan alat bantu Gephi):

graf

Maka node ke A memiliki bobot CD(A)=2/3, yaitu jumlah edge yang terbentuk pada node A dengan node lain di bagi dengan jumlah node dalam graf dikurangi 1. Sedangkan untuk node B memiliki bobot CD(B)=3/3.

Berikutnya adalah closeness centrality yang akan menghitung bobot centrality sebuah node berdasar jumlah jarak terpendek antara node i dengan node lainnya. Untuk menghitung bobot closeness centrality setiap node, kita dapat menggunakan rumus normalisasi sebagai berikut :

closeness

Dari contoh graf di atas, maka kita dapat menghitung bobot closeness centrality untuk node A adalah CC(A) = 3/(1+2+1) = 0.75. Sedangkan untuk CC(B) = 3/(1+1+1) = 1.

Terakhir adalah betweenness centrality yang akan menghitung bobot setiap node berdasar seberapa banyak node i dilalui oleh dua node lain dalam graf berdasar jalur terpendeknya. Perhitungan bobot betweenness centrality untuk setiap node dapat menggunakan rumus sebagai berikut :

betweenness

Pjk(i) adalah jumlah jalur terpendek antara node j dan k yang melewati i, sedangkan Pjk adalah jumlah jalur terpendek antara j dan k.

Sekali lagi berdasar graf di atas, maka kita dapat menghitung bobot CB(A) = CB(C) = 0, sedangkan CB(B) = CB(D) = (2 * 0.5)/(3*2) = 1/6.

Demikian contoh perhitungan sederhana untuk ketiga metode dasar penghitungan bobot centrality. Semoga bermanfaat.

About these ads