Tugas 6 - page range

Tugas 6 - page range#

Algoritma PageRank dengan Pendekatan Sistem Dinamis#

Pendahuluan#

Algoritma PageRank adalah metode yang digunakan oleh mesin pencari Google untuk menentukan peringkat halaman web berdasarkan jumlah dan kualitas tautan yang menuju ke halaman tersebut. Dalam penjelasan ini, kita akan membahas bagaimana PageRank bekerja menggunakan pendekatan sistem dinamis dan menyertakan contoh soal beserta penyelesaiannya, termasuk solusi menggunakan Python.

Konsep Dasar PageRank#

PageRank bekerja berdasarkan prinsip bahwa halaman yang lebih penting akan menerima lebih banyak tautan dari halaman lain. Peringkat awal didistribusikan secara merata di antara semua halaman. Pada setiap iterasi, peringkat halaman diperbarui berdasarkan peringkat halaman yang menautkannya.

Langkah-langkah Algoritma PageRank#

1. Distribusi Awal#

Pada awalnya, kepentingan (PageRank) setiap halaman web didistribusikan secara merata. Misalnya, jika ada 4 halaman web, maka setiap halaman akan memiliki nilai awal PageRank sebesar 1/4 atau 0.25. Vektor peringkat awal, $(\mathbf{v})$, adalah: $$ {v} = \begin{pmatrix} 0.25 \\ 0.25 \\ 0.25 \\ 0.25 \end{pmatrix} $$

2. Matriks Transisi#

Matriks transisi $(A)$ menggambarkan kemungkinan berpindah dari satu halaman ke halaman lain melalui tautan. Misalkan kita memiliki matriks transisi $(A)$ sebagai berikut:

\[\begin{split} A = \begin{pmatrix} 0 & 0 & 1 & 0.5 \\ 0.5 & 0 & 0.5 & 0 \\ 0.5 & 0.5 & 0 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ \end{pmatrix} \end{split}\]

Setiap elemen $(A_{ij})$ dalam matriks ini menunjukkan probabilitas berpindah dari halaman $(j)$ ke halaman $(i)$.

3. Iterasi Pembaruan Peringkat#

Untuk memperbarui nilai PageRank, kita kalikan matriks transisi $(A)$ dengan vektor peringkat saat ini $(\mathbf{v})$. Proses ini diulangi beberapa kali hingga nilai PageRank konvergen atau stabil.

Iterasi Pertama#

\[\begin{split} \mathbf{Av} = A \cdot \mathbf{v} = \begin{pmatrix} 0.37 \\ 0.08 \\ 0.33 \\ 0.20 \end{pmatrix} \end{split}\]

Di sini, kita mengalikan matriks (A) dengan vektor (\mathbf{v}) untuk mendapatkan vektor peringkat yang baru.

Iterasi Kedua#

\[\begin{split} A^2 \mathbf{v} = A \cdot (\mathbf{Av}) = \begin{pmatrix} 0.43 \\ 0.12 \\ 0.27 \\ 0.16 \end{pmatrix} \end{split}\]

Kita ulangi proses ini dengan mengalikan matriks A dengan hasil dari iterasi sebelumnya.

Iterasi Selanjutnya#

Proses ini dilanjutkan hingga vektor peringkat tidak berubah secara signifikan antara iterasi, yang menunjukkan bahwa PageRank telah mencapai keseimbangan. Berikut adalah hasil beberapa iterasi berikutnya:

\[\begin{split} A^3 \mathbf{v} = \begin{pmatrix} 0.35 \\ 0.14 \\ 0.29 \\ 0.20 \end{pmatrix} A^4 \mathbf{v} = \begin{pmatrix} 0.39 \\ 0.11 \\ 0.29 \\ 0.19 \end{pmatrix} A^5 \mathbf{v} = \begin{pmatrix} 0.39 \\ 0.11 \\ 0.29 \\ 0.19 \end{pmatrix} A^6 \mathbf{v} = \begin{pmatrix} 0.38 \\ 0.13 \\ 0.29 \\ 0.19 \end{pmatrix} A^7 \mathbf{v} = \begin{pmatrix} 0.38 \\ 0.12 \\ 0.29 \\ 0.19 \end{pmatrix} A^8 \mathbf{v} = \begin{pmatrix} 0.38 \\ 0.12 \\ 0.29 \\ 0.19 \end{pmatrix} \end{split}\]

4. Konvergensi#

Setelah beberapa iterasi, vektor peringkat stabil pada nilai tertentu. Ini disebut sebagai nilai keseimbangan atau PageRank akhir. Nilai PageRank akhir adalah:

\[\begin{split} {v^*} = \begin{pmatrix} 0.38 \\ 0.12 \\ 0.29 \\ 0.19 \end{pmatrix} \end{split}\]

kita akan mengganti nilai awal vektor peringkat $(\mathbf{v})$ dengan nilai yang berbeda dan melihat bagaimana iterasi PageRank bekerja. Misalkan kita mulai dengan distribusi awal yang berbeda, seperti: $$ \mathbf{v}= \begin{pmatrix} 0.4 \\ 0.3 \\ 0.2 \\ 0.1 \end{pmatrix} $$

Berikut adalah penjelasan dan penyelesaian lengkap dengan perubahan nilai awal vektor peringkat.

Contoh Soal dan Penyelesaian#

Soal#

Misalkan kita memiliki empat halaman web A, B, C, dan D dengan tautan sebagai berikut:

A menautkan ke B dan D
B menautkan ke A dan D
C menautkan ke B dan D
D menautkan ke C

Buat matriks transisi A dan hitung nilai PageRank setelah beberapa iterasi menggunakan algoritma PageRank dengan nilai awal vektor peringkat $(\mathbf{v})$ sebagai

\[\begin{split} \begin{pmatrix} 0.4 \\ 0.3 \\ 0.2 \\ 0.1 \end{pmatrix} \end{split}\]

Penyelesaian#

Matriks Transisi (A):

\[\begin{split} A = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0 & 0 & 1 \\ 0.5 & 0 & 0.5 & 0 \\ \end{pmatrix} \end{split}\]

Distribusi Awal: $$ {v} = \begin{pmatrix} 0.4 \\ 0.3 \\ 0.2 \\ 0.1 \end{pmatrix} $$
Iterasi Pembaruan Peringkat: $$ f{Av} = A \cdot \mathbf{v} = \begin{pmatrix} 0.3 \\ 0.3 \\ 0.1 \\ 0.3 \end{pmatrix} $$

\

\[\begin{split} A^2 \mathbf{v} = A \cdot (\mathbf{Av}) = \begin{pmatrix} 0.3 \\ 0.2 \\ 0.3 \\ 0.2 \end{pmatrix} \end{split}\]

\

\[\begin{split} A^3 \mathbf{v} = A \cdot (A^2 \mathbf{v}) = \begin{pmatrix} 0.2 \\ 0.3 \\ 0.2 \\ 0.3 \end{pmatrix} \end{split}\]

\

\[\begin{split} A^4 \mathbf{v} = A \cdot (A^3 \mathbf{v}) = \begin{pmatrix} 0.3 \\ 0.2 \\ 0.3 \\ 0.2 \end{pmatrix} \end{split}\]

Konvergensi: Setelah beberapa iterasi, nilai PageRank tidak berubah signifikan dan tetap sama, yaitu: $$ \mathbf{v^*} = \begin{pmatrix} 0.3 \\ 0.2 \\ 0.3 \\ 0.2 \end{pmatrix} $$

Dalam kasus ini, nilai PageRank akhirnya menunjukkan bahwa halaman A dan C memiliki kepentingan yang sama, sedangkan halaman B dan D juga memiliki kepentingan yang sama namun lebih rendah dibandingkan A dan C.

Penyelesaian dengan Python#

Berikut adalah implementasi PageRank menggunakan Python dengan nilai awal vektor peringkat $(\mathbf{v})$ sebagai $$ \begin{pmatrix} 0.4 \\ 0.3 \\ 0.2 \\ 0.1 \end{pmatrix} $$

import numpy as np

# Matriks Transisi
A = np.array([
    [0, 1, 0, 0],
    [0.5, 0, 0.5, 0],
    [0, 0, 0, 1],
    [0.5, 0, 0.5, 0]
])

# Distribusi Awal
v = np.array([0.4, 0.3, 0.2, 0.1])

# Jumlah Iterasi
num_iterations = 100

# Iterasi Pembaruan Peringkat
for i in range(num_iterations):
    v = np.dot(A, v)

print("Nilai PageRank akhir:")
print(v)

Nilai PageRank akhir:
[0.3 0.2 0.3 0.2]

Kode ini menunjukkan bahwa setelah beberapa iterasi, nilai PageRank untuk setiap halaman adalah 0.3 untuk halaman A dan C, serta 0.2 untuk halaman B dan D, yang mencerminkan distribusi kepentingan dalam jaringan berdasarkan struktur tautan.

Kesimpulan#

Nilai PageRank akhir memberikan ukuran kepentingan relatif dari setiap halaman web dalam jaringan berdasarkan tautan yang diterimanya. Algoritma PageRank dengan pendekatan sistem dinamis ini membantu mesin pencari seperti Google menentukan halaman web mana yang lebih relevan atau penting berdasarkan struktur tautan. Dengan memahami cara kerja PageRank dan menggunakan contoh serta implementasi Python ini, kita dapat mengoptimalkan halaman web untuk mendapatkan peringkat yang lebih baik dalam hasil pencarian.

import numpy as np
a = np.array ([[0,0,1,1/2],[1/3,0,0,0],[1/3,1/2,0,1/2],[1/3,1/2,0,0]])
v = np.array ([[0,25],[0,25],[0,25],[0,25]])

v1 = a@v
print("v1 adalah  : ")
print(v1)
print("===========================")
v2 = a@v1
print("v2 adalah : ")
print(v2)
v3 = a@v2
print("v3 adalah  : ")
print(v3)
print("===========================")
v4 = a@v3
print("v4 adalah  : ")
print(v4)
print("===========================")
v5 = a@v4
print("v5 adalah  : ")
print(v5)
print("===========================")
v6 = a@v5
print("v6 adalah  : ")
print(v6)
print("===========================")
v7 = a@v6
print("v7 adalah  : ")
print(v7)
print("===========================")
v8 = a@v7
print("v8 adalah  : ")
print(v8)
print("===========================")
print(v8.round(1))

v1 adalah  : 
[[ 0.         37.5       ]
 [ 0.          8.33333333]
 [ 0.         33.33333333]
 [ 0.         20.83333333]]
===========================
v2 adalah : 
[[ 0.         43.75      ]
 [ 0.         12.5       ]
 [ 0.         27.08333333]
 [ 0.         16.66666667]]
v3 adalah  : 
[[ 0.         35.41666667]
 [ 0.         14.58333333]
 [ 0.         29.16666667]
 [ 0.         20.83333333]]
===========================
v4 adalah  : 
[[ 0.         39.58333333]
 [ 0.         11.80555556]
 [ 0.         29.51388889]
 [ 0.         19.09722222]]
===========================
v5 adalah  : 
[[ 0.         39.0625    ]
 [ 0.         13.19444444]
 [ 0.         28.64583333]
 [ 0.         19.09722222]]
===========================
v6 adalah  : 
[[ 0.         38.19444444]
 [ 0.         13.02083333]
 [ 0.         29.16666667]
 [ 0.         19.61805556]]
===========================
v7 adalah  : 
[[ 0.         38.97569444]
 [ 0.         12.73148148]
 [ 0.         29.05092593]
 [ 0.         19.24189815]]
===========================
v8 adalah  : 
[[ 0.         38.671875  ]
 [ 0.         12.99189815]
 [ 0.         28.97858796]
 [ 0.         19.35763889]]
===========================
[[ 0.  38.7]
 [ 0.  13. ]
 [ 0.  29. ]
 [ 0.  19.4]]