Algoritma Page Rank

Algoritma Page Rank adalah salah satu algoritma yang digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah mengenai pencarian nilai masing-masing halaman yang tersedia pada sebuah website.

Diasumsikan ada sebuah website yang memliki 5 halaman, yaitu halaman A, B, C, D, E
Masing-masing halaman memiliki satu atau beberapa tautan menuju halaman yang lain
Hitung nilai page rank untuk masing-masing halaman
Diasumsikan data tautan yang tersedia adalah sebagai berikut

Jika diilustrasikan dalam gambar, maka model data awal adalah sebagai berikut

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah titik yang digunakan
Diasumsikan dalam kasus ini, jumlah titik ada 5 buah

Const jumlahTitik As Integer = 5

* Tentukan faktor damp yang digunakan
Diasumsikan dalam kasus ini, nilai faktor damping adalah 0.85

Const faktorDamp As Double = 0.85

Langkah-langkah penggunaan algoritma ini adalah

1. Inisialisasi semua variabel yang diperlukan, yaitu variabel gambar, titik, dan garis
Penjelasan tentang masing-masing class akan dijelaskan pada skrip dibawah ini

Dim gmb As New Gambar(jumlahTitik)
Dim daftarTitik As List(Of Titik) = gmb.daftarTitik
Dim daftarGaris As New List(Of Garis)()
Dim grs As Garis

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah 3 buah class
Class Titik digunakan untuk menampung data titik, jumlah tautan, dan nilai page rank
Class Garis digunakan untuk menampung data titik awal dan titik tujuan
Class Gambar digunakan untuk menampung semua data titik dan semua data garis yang digunakan
Deklarasi masing-masing class adalah sebagai berikut:

Public Class Gambar
    Public daftarTitik As List(Of Titik) = Nothing
    Public daftarGaris As List(Of Garis) = Nothing

    Public Sub New(jumlahTitik As Integer)
        daftarTitik = New List(Of Titik)
        For i As Integer = 0 To jumlahTitik - 1
            daftarTitik.Add(New Titik(i))
        Next
    End Sub
End Class

Public Class Garis
    Private m_titikAwal As Titik
    Private m_titikTujuan As Titik

    Public Property titikAwal() As Titik
        Get
            Return m_titikAwal
        End Get
        Set(value As Titik)
            m_titikAwal = value
        End Set
    End Property

    Public Property titikTujuan() As Titik
        Get
            Return m_titikTujuan
        End Get
        Set(value As Titik)
            m_titikTujuan = value
        End Set
    End Property

    Public Sub New(titikAwal As Titik, titikTujuan As Titik)
        m_titikAwal = titikAwal
        m_titikTujuan = titikTujuan
    End Sub
End Class

Public Class Titik
    Private m_Idx As String
    Private m_jumlahTautan As Integer
    Private m_pageRank As Double

    Public Property Idx() As String
        Get
            Return m_Idx
        End Get
        Set(value As String)
            m_Idx = value
        End Set
    End Property

    Public Property JumlahTautan() As Integer
        Get
            Return m_jumlahTautan
        End Get
        Set(value As Integer)
            m_jumlahTautan = value
        End Set
    End Property

    Public Property PageRank() As Double
        Get
            Return m_pageRank
        End Get
        Set(value As Double)
            m_pageRank = value
        End Set
    End Property

    Public Sub New(ByVal idx As Integer)
        m_Idx = idx
        m_jumlahTautan = 0
        m_pageRank = 0
    End Sub
End Class

2. Masukkan data titik dan garis kedalam masing-masing variabel yang tersedia

grs = New Garis(daftarTitik(0), daftarTitik(1))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(0), daftarTitik(4))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(2))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(3))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(4))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(2), daftarTitik(1))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(3), daftarTitik(2))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(4), daftarTitik(2))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(4), daftarTitik(3))
daftarGaris.Add(grs)

3. Hitung jumlah tautan dari masing-masing titik yang terhubung oleh garis
Tautan hanya dihitung dari titik awal saja karena tautan hanya bersifat searah (bukan 2 arah)

For i As Integer = 0 To daftarGaris.Count - 1
	Dim garis As Garis = daftarGaris(i)
	garis.titikAwal.JumlahTautan += 1
Next

4. Lakukan perhitungan pada masing-masing titik sampai kondisi berhenti ditemukan (poin 4a – 4c)

Dim isSelesai As Boolean = False
Do While Not isSelesai
	iterasi += 1
	. . .

4a. Simpan nilai page rank dari masing-masing titik pada perulangan sebelumnya

Dim nilaiPageRankSebelumnya(jumlahTitik - 1) As Double
For i As Integer = 0 To jumlahTitik - 1
	nilaiPageRankSebelumnya(i) = daftarTitik(i).PageRank
Next

4b. Lakukan perhitungan pada masing-masing titik (poin 4b1 – 4b2)

For i As Integer = 0 To jumlahTitik - 1
	. . .

4b1. Lakukan perhitungan pada masing-masing garis
Jika terdapat garis dengan titik tujuan adalah titik yang sedang dihitung,
maka hitung nilai page rank bagian dari titik tersebut dengan rumus:
PR(i) = PR(j)/ jumlahTautan(j)
Kemudian jumlahkah semua nilai page rank untuk setiap titik yang ditemukan

For j As Integer = 0 To daftarGaris.Count - 1
	Dim garis As Garis = daftarGaris(j)
	If garis.titikTujuan.Idx = i Then
		tmpNilaiPageRank += garis.titikAwal.PageRank / garis.titikAwal.JumlahTautan
	End If
Next

4b2. Masukkan faktor damping ke dalam nilai page rank dengan rumus:
PR(i) = (1 – d) / N + d * PR(i)
Kemudian masukkan nilai yang baru sebagai nilai page rank untuk titik yang sedang dihitung

tmpNilaiPageRank = (1 - faktorDamp) / jumlahTitik + faktorDamp * tmpNilaiPageRank
daftarTitik(i).PageRank = tmpNilaiPageRank

4c. Lakukan perhitungan pada masing-masing titik
Jika ditemukan nilai page rank dari sebuah titik yang masih berbeda dengan nilai page rank pada perhitungan sebelumnya.
maka ulangi perhitungan ini dari awal

isSelesai = True
For i As Integer = 0 To jumlahTitik - 1
	If Math.Abs(daftarTitik(i).PageRank - nilaiPageRankSebelumnya(i)) > EPSILON Then
		isSelesai = False
		Continue Do
	End If
Next

5. Catat hasil akhir untuk masing-masing nilai page rank yang ditemukan

Console.WriteLine(vbCrLf & "Hasil akhir: ")
For i As Integer = 0 To jumlahTitik - 1
	Console.WriteLine("Nilai Page Rank dari halaman " & Chr(i + 65) & " adalah " & daftarTitik(i).PageRank.ToString("F6"))
Next

Hasil akhir adalah: (klik untuk perbesar gambar)

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut

Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.