Google PageRank: Ini Rumus (Formula)-nya

Dari Wikipedia

PageRank Matematis (dari 100) untuk suatu jaringan sederhana (PageRank yang dilaporkan Google dihitung ulang secara logaritmik). Halaman C memiliki PageRank lebih tinggi dari halaman E, walaupun ia memiliki lebih sedikit link yang mengarah kepadanya; link yang dimilikinya memiliki nilai jauh lebih tinggi. Seorang surfer yang memilih link acak pada setiap halaman (tetapi dengan 15% kemungkinan loncat ke halaman acak di web) akan tiba di halaman E dengan kemungkinan 8,1%.  (15% kemungkinan loncat ke halaman lain adalah karena damping factor sebesar 85%). Tanpa damping, semua web surfer akhirnya akan tiba di halaman A,B, atau C, dan semua halaman lain akan memiliki PageRank 0 (nol). Halaman A dianggap memiliki link ke semua halaman di web, karena ia tidak memiliki outgoing link sama sekali.

PageRank berdasar pada demokrasi web. Ia menggunakan struktur link yang sangat-sangat besar sebagai indikator nilai masing-masing halaman. Pada dasarnya Google menafsirkan sebuah link dari halaman A ke halaman B sebagai vote, oleh halaman A, ke halaman B. Tetapi Google tidak hanya melihat jumlah vote, atau link yang diterima suatu halaman; Google juga menganalisis kualitas halaman yang memberikan vote. Vote yang diberikan oleh halaman yang “penting”, bernilai lebih tinggi dan membantu halaman lain menjadi “penting”.

Dengan kata lain, PageRank dihasilkan dari “surat suara” antar semua halaman di World Wide Web mengenai seberapa penting sebuah halaman web. Satu hyperlink ke satu halaman dihitung sebagai satu vote. PageRank suatu halaman ditentukan secara rekursif dan bergantung pada jumlah dan metrik PageRank semua halaman yang merujuk pada halaman tsb. Halaman yang di-link oleh banyak halaman yang memiliki PageRank tinggi menjadi tinggi pula rank-nya. Jika tidak ada link yang merujuk ke suatu halaman maka tidak ada dukungan (vote) sama sekali untuk halaman itu.

Google menggunakan angka 0-10 untuk menandai setiap halaman web di Internet; angka PageRank ini menyatakan nilai pentingnya suatu halaman web di mata Google. PageRank dihasilkan dari nilai probabilitas teoritis dengan skala logaritmik seperti Skala Richter. PageRank suatu halaman web didasarkan pada (1) kuantitas inbound link dan (2) PageRank halaman yang memberikan link. Faktor-faktor lain, seperti (3) relevansi frasa pencarian (search words) yang ada pada suatu halaman dan (4) kunjungan nyata (actual visit) ke suatu halaman yang dilaporkan oleh Google Toolbar juga mempengaruhi PageRank.

Algoritma

PageRank adalah sebaran peluang (probability distribution) yang digunakan untuk menyatakan kemungkinan  klik-klik acak yang dilakukan seseorang tiba pada suatu halaman web tertentu. PageRank dapat dihitung pada kumpulan dokumen seberapapun besarnya koleksi dokumen tsb. Diasumsikan, di awal komputasi sebaran ini terbagi rata di antara semua dokumen yang ada dalam suatu kumpulan (set). Komputasi PageRank memerlukan beberapa tahapan yang disebut “iterasi” terus menerus dalam set dokumen agar didapat nilai PageRank yang lebih dekat mencerminkan nilai teoritis sebenarnya.

Peluang dinyatakan dengan nilai numerik antara 0 dan 1. Peluang 0,5 biasa dikatakan sebagai “50% kemungkinan” terjadinya sesuatu. Oleh karena itu PageRank 0,5 berarti ada 50% kemungkinan seseorang yang meng-klik suatu link acak akan terarah dan tiba di dokumen dengan PageRank 0,5.

Simplified algorithm

How PageRank Works

Bayangkan suatu universe kecil berisi empat halaman web: A, B, C, D. Nilai perkiraan awal PageRanknya akan terbagi rata di antara keempat dokumen ini. Artinya, masing-masing dokumen memiliki modal awal PageRank 0,25.

Pada PageRank versi awal, nilai awalnya adalah 1. Ini berarti jumlah (sum) semua halaman adalah keseluruhan (total number) halaman di web. PageRank versi berikutnya mengasumsikan distribusi peluang antara 0 dan 1. Di sini digunakan sebaran peluang sederhana (simple probability distribution)- jadi  nilai awalnya adalah 0,25.

Jika halaman B, C, dan D masing-masing hanya me-link ke A, masing-masing akan menyumbang PageRank 0,25 ke A. Oleh karena itu semua PageRank PR() pada sistem sederhana ini akan terkumpul di A karena semua link menuju ke A.

PageRank A = PageRank B + PageRank C + PageRank D

PR(A) = 0,25 + 0,25 + 0,25

PR(A) = 0,75

Lagi, misalkan halaman B juga memiliki link ke halaman C, dan halaman D memiliki link ke ketiga halaman. Nilai link-vote terbagi di antara semua outbound link pada suatu halaman. Jadi halaman B memberi vote senilai 0,125 ke halaman A dan vote senilai 0,125 ke halaman C. Hanya sepertiga PageRank D dihitung untuk PageRank A (kira-kira 0,083)

Nilai PageRank awal masing-masing halaman = 1/4 = 0,25

PR(A) = (0,25/2) + (0,25/1) + (0,25/3)

PR(A) = 0,125 + 0,25 + 0,083

PR(A) = 0,485

Dengan kata lain, PageRank yang diberikan oleh suatu outbound link sama dengan nilai PageRank dokumen dibagi jumlah outbound link L() (dengan asumsi bahwa link ke URL tertentu hanya ada satu per dokumen)

Secara umum, nilai PageRank untuk setiap halaman u dapat dinyatakan:

,

Nilai PageRank halaman u bergantung pada nilai PageRank masing-masing halaman v dari set Bu (set ini berisi semua halaman yang me-link ke halaman u), dibagi jumlah L(v) (outbound link) dari halaman v.

Damping Factor

Teori PageRank mengatakan bahwa seorang peselancar imaginer (imaginary surfer) yang secara acak meng-klik link  pada akhirnya akan berhenti melakukan klik. Peluang seseorang akan melanjutkan klik-nya disebut damping factor d. Berbagai studi telah dilakukan untuk menguji damping factor, tetapi umumnya diasumsikan bahwa damping factor akan ditetapkan sekitar 0,85.

Damping factor dikurangkan dari 1 (dan dalam beberapa varian algoritma, hasilnya dibagi dengan jumlah dokumen (N) yang ada dalam kumpulan) lalu ditambahkan ke hasil dari perkalian damping factor dengan jumlah nilai PageRank yang diterima:

Jadi PageRank suatu halaman sebagian besar berasal dari PageRank halaman-halaman lain. Damping faktor mengurangi nilai yang didapat. Paper awal (original paper) mengenai PageRank, memberikan rumus dibawah, yang menimbulkan kesulitan:

Perbedaan antara kedua rumus itu adalah bahwa nilai PageRank pada rumus pertama jumlah akhirnya adalah satu, sementara pada rumus kedua masing-masing PageRank dikalikan dengan N dan hasilnya N. Pernyataan dalam paper Larry Page dan Sergey Brin bahwa “jumlah semua PageRank adalah satu” dan diklaim oleh pegawai Google lainnya, mendukung varian pertama dari rumus di atas.

Google menghitung ulang nilai PageRank setiap kali melakukan crawl di Web dan menyusun ulang indeksnya. Sejalan meningkaktnya jumlah dokumen dalam koleksinya, nilai awal PageRank semua dokumen berkurang.

Rumus di atas menggunakan model random surfer yang menjadi bosan setelah beberapa klik dan pindah ke halaman acak lainnya. Nilai PageRank suatu halaman mencerminkan kemungkinan seorang surfer tiba pada suatu halaman dengan meng-klik suatu link.

If a page has no links to other pages, it becomes a sink and therefore terminates the random surfing process. However, the solution is quite simple. If the random surfer arrives at a sink page, it picks another URL at random and continues surfing again.

Jika suatu halaman tidak memiliki link ke halaman lain, halaman ini menjadi jalan buntu (sink) dan oleh karenanya menghentikan proses random surfing. Tetapi solusinya cukup sederhana. Jika si random surfer tiba pada suatu halaman buntu, ia meng-klik URL lain secara acak dan berlanjut berselancar lagi.

Dalam penghitungan PageRank, halaman yang tidak memiliki outbound link dianggap me-link ke semua halaman dalam set. Nilai PageRank-nya oleh karena itu dibagi rata di antara semua halaman. Dengan kata lain, agar fair dengan halaman-halaman yang tidak buntu, transisi acak ini ditambahkan ke semua node dalam Web, dengan peluang residual biasanya d = 0,85, dihitung kira-kira dari frekuensi penggunaan fitur bookmark yang digunakan peselancar.

Persamaannya menjadi sbb:

dimana p₁,p₂,…,p_N adalah halaman yang diperhitungkan, M(p_i) adalah set halaman yang me-link ke p_i, L(p_j) adalah jumlah outbound link pada halaman p_j, dan N adalah keseluruhan (total number) halaman.

Home | About | Blogging | Daily Life | Insights | News | Videos | SEO