Dalam artikel kali ini saya akan menjelaskan definisi dari google pagerank menggunakan program dari javascript agar lebih mudah dimengerti bagaimana si om google memberikan nilai pagerank terhadap suatu website atau blog.
Mudah-mudahan dengan program ini, anda bisa lebih mengerti lagi tentang google pagerank.
Saya akan menjelaskan sistem kerja program ini secara bertahap-tahap.
Apa itu pagerank?
Mungkin banyak dari anda yang mengerti tentang pagerank, tapi tidak salah juga jika saya akan mengulas kembali artian dari google pagerank.
Menurut Wikipedia pagerank adalah sebuah algoritma yang telah dipatenkan yang berfungsi menentukan situs web mana yang lebih penting/populer. PageRank merupakan salah satu fitur utama mesin pencari Google dan diciptakan oleh pendirinya, Larry Page dan Sergey Brin yang merupakan mahasiswa Ph.D. Universitas Stanford.
Sebelumnya, kita harus memahami beberapa metode yang akan digunakan seperti:
- Graph (Grafik)
- Adjacency Matrix
- Row Stochastic Matrix
- Eigenvector Centrality
- Power Iteration
1. Graph
Grafik/graph adalah representasi abstrak dari satu set objek yang dihubungkan dengan garis. Obyek disebut sebagai node (atau vektor) dan koneksi mereka sebagai ujungnya.
Ada dua jenis utama dari grafik. Grafik yang tidak diarahkan dan grafik yang diarahkan. Sebuah grafik yang diarahkan adalah salah satu tempat tepi antara dua node dianggap sama.
Hubungan antara grafik dengan Pagerank
PageRank adalah properti matematika tertentu dari grafik yang menggambarkan jaringan halaman dan link mereka. Kita tidak bisa benar-benar memahami konsep ini kecuali kita langsung terlibat dalam matematika.
Ada sejumlah cara matematis setara dengan memecahkan PageRank dari grafik mewakili struktur link dari jaringan halaman web. Pendekatan yang lebih mudah dipahamai adalah dengan menggunakan matriks.
Bila menggunakan matriks untuk menghitung PageRank kita mengukur sentralitas vektor eigen dari matriks dimodifikasi berdasarkan jaringan.
2. Adjacency Matrix
Untuk melakukan perhitungan apapun kita harus menjelaskan jaringan halaman web saling terhubung dalam semacam bahasa matematis. Antara lain, kita akan menggunakan bahasa matriks. Cabang matematika yang berhubungan dengan matriks disebut aljabar linear .
Apa itu matriks?
Secara sederhana, matriks adalah array persegi panjang elemen. Memiliki jumlah baris dan jumlah kolom. Matriks digunakan untuk sejumlah tujuan yang berbeda dan merupakan landasan matematika komputasi. Hampir setiap topik lanjutan dalam ilmu komputer, dari grafis 3D, AI, untuk analisis jaringan seperti PageRank melibatkan matriks.
Matriks dimulai sebagai cara untuk memecahkan sistem persamaan linear tetapi sesekali matriks itu sendiri dikembangkan dan terpisah dan diperluas untuk aplikasi lain.
Ini jelas berkaitan dengan algoritma PageRank.
Berikut adalah contoh matriks 11 x 11 yang akan dicontohkan dalam jaringan suatu website atau blog dalam pemberian nilai pagerank.
| X | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 9 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 10 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 11 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
Sebagai contoh dari data tabel di atas,
halaman 1 tidak memiliki link ke halaman manapun, sedangkan
halaman 2 memberikan link kepada
halaman 3 atau juga sebaliknya.
Grid ini disebut sebagai
matriks adjacency dari grafik yang menggambarkan jaringan halaman web.
Dari data tabel di atas sekarang kita akan menerjemahkannya ke bahasa pemrograman komputer. Dalam contoh ini kita menggunakan javaScript library yang disebut Sylvester. Ia memiliki sejumlah kelas yang memungkinkan kita untuk membentuk matriks dan vektor di sejumlah dimensi.
Dalam istilah pemrograman, matriks mirip dengan
array dari array.
adjacencyMatrix = $M([
[0,0,0,0,0,0,0,0,0,0,0],
[0,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,0,0,0,0],
[1,1,0,0,0,0,0,0,0,0,0],
[0,1,0,1,0,1,0,0,0,0,0],
[0,1,0,0,1,0,0,0,0,0,0],
[0,1,0,0,1,0,0,0,0,0,0],
[0,1,0,0,1,0,0,0,0,0,0],
[0,1,0,0,1,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0,0,0,0]
]);
Untuk sisa artikel ini, kita akan menambahkan fungsi ke dalam Matriks Sylvester.
3. Row Stochastic Matrix
PageRank juga dapat dianggap sebagai representasi dari seberapa besar kemungkinan itu adalah bahwa seseorang secara acak mengklik link baik berada pada halaman tertentu, kita perlu mengkonversi matriks ke representasi yang mewakili probabilitas.
Misalnya, sejak
Halaman 5 memiliki 3 link di atasnya, ada 1 di 3 kemungkinan bahwa kita akan secara acak klik pada salah satu link tersebut.
Jenis matriks ini dikenal sebagai matriks stokastik , dan dalam kasus ini kita akan mencari matriks stokastik baris. Artinya, kita ingin setiap baris untuk menambahkan hingga 1. Kita akan kembali merepresentasi dari jaringan link di atas ke bentuk yang mengambil ke akun probabilitas bahwa pengguna acak akan browse ke halaman tertentu.
| X | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1.00 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 1.00 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0.50 | 0.50 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0.30 | 0 | 0.30 | 0 | 0.30 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0.50 | 0 | 0 | 0.50 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0.50 | 0 | 0 | 0.50 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | 0 | 0.50 | 0 | 0 | 0.50 | 0 | 0 | 0 | 0 | 0 | 0 |
| 9 | 0 | 0.50 | 0 | 0 | 0.50 | 0 | 0 | 0 | 0 | 0 | 0 |
| 10 | 0 | 0 | 0 | 0 | 1.00 | 0 | 0 | 0 | 0 | 0 | 0 |
| 11 | 0 | 0 | 0 | 0 | 1.00 | 0 | 0 | 0 | 0 | 0 | 0 |
Namun, apa yang terjadi jika ada halaman yang bertindak sebagai penyerap, yaitu tidak memiliki link keluar atau disebut juga
outbound links? Bagaimana halaman ini dapat terpengaruh dari perhitungan?
Jika kita secara acak tersandung di halaman web langka yang tidak memiliki link ke halaman lain kita akan mengasumsikan bahwa kita memiliki probabilitas yang sama di salah satu halaman web lain dalam jaringan. Artinya, kita akan mengasumsikan bahwa ada link ke setiap halaman dari halaman yang tidak memiliki link.
Agar adil buat halaman lainnya yang memiliki link, acak transisi ini ditambahkan ke semua halaman di jaringan, dengan peluang sisa tambahan yang disebut faktor redaman.
Faktor redaman disertakan untuk meningkatkan kemungkinan bahwa kita akan berakhir di halaman dengan sentralitas jaringan yang lebih dan melawan beberapa pelanggaran yang bisa spammer gunakan untuk permainan algoritma ini.
Baik penyesuaian yang dibuat untuk halaman menjuntai atau faktor redaman diperlukan untuk menghitung sentralitas jaringan.
Berikut adalah fungsi yang menghitung matriks stokastik baris:
Matrix.prototype.row_stochastic = function(damping_factor) {
var row_length = this.elements[0].length;
[hg] var d = (1 - damping_factor) / row_length;[/hg]
var row_total = [];
[hg] for (var x = 0; x < row_length; x++) {
row_total.push(0);
for (y = 0; y < row_length; y++) {
row_total[x] += this.elements[x][y];
}
}[/hg]
var a1 = this.elements.clone();
[hg] for (var x = 0; x < row_length; x++) {
for (var y = 0; y < row_length; y++) {
if (row_total[x] > 0) {
a1[x][y] = a1[x][y]/row_total[x] + d;
}
else {
a1[x][y] = (1/row_length) + d;
}
}
}[/hg]
return $M(a1);
}
Perhatikan bagian yang sudah saya highlight, disana akan menghitung probabilitas tambahan bergerak dari satu halaman ke halaman lain sebagai variabel yang disebut
d, yang didasarkan pada faktor redaman dan jumlah total halaman web.
Selanjutnya, kita iterasi melalui setiap baris dan menyimpan array jumlah semua elemen dalam baris, seperti yang terlihat pada bagian pengulangan
for pertama yang telah di highlight.
Selanjutnya kita kembali iterasi setiap baris, kali ini membagi setiap elemen dengan total baris program, memenuhi persyaratan stokastik kita. Kita juga menambahkan variabel
d tidak hanya untuk halaman yang tidak memiliki outbound link (karena itu diasumsikan link ke semua halaman. Agar adil bagi halaman yang memiliki link cara ini akan dilakukan pada fungsi
for kedua yang telah di highlight.
Bila menggunakan faktor redaman dengan nilai 0.825 matriks yang dihasilkan adalah:
| X | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 1 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 |
| 2 | 0.02 | 0.02 | 1.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 |
| 3 | 0.02 | 1.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 |
| 4 | 0.52 | 0.52 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 |
| 5 | 0.02 | 0.32 | 0.02 | 0.32 | 0.02 | 0.32 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 |
| 6 | 0.02 | 0.52 | 0.02 | 0.02 | 0.52 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 |
| 7 | 0.02 | 0.52 | 0.02 | 0.02 | 0.52 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 |
| 8 | 0.02 | 0.52 | 0.02 | 0.02 | 0.52 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 |
| 9 | 0.02 | 0.52 | 0.02 | 0.02 | 0.52 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 |
| 10 | 0.02 | 0.02 | 0.02 | 0.02 | 1.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 |
| 11 | 0.02 | 0.02 | 0.02 | 0.02 | 1.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 |
4. Eigenvector Centrality
PageRank adalah ukuran sentralitas jaringan dengan beberapa tweak yang dibuat khusus untuk web browsing, seperti yang kita bahas di atas. Karena kita cukup banyak berurusan dengan matriks pada titik ini kita akan lihat sebagai sentralitas vektor eigen.
Sentralitas vektor eigen adalah properti dari grafik awal dari jaringan halaman web.
Apa itu vektor?
Pada tingkat yang paling abstrak, vektor lebih dari anggota ruang vektor apapun.
Sebuah vektor pada ruang vektor 2D, yang disebut vektor euclidean adalah objek geometri yang memiliki besar dan arah. Dalam kasus komputer grafis 2D hubungan pixel satu sama lain dalam foto dapat dianggap vektor.
Vektor ditindaklanjuti oleh matriks. Kita bisa memikirkan jika matriks seperti fungsi yang bisa kita terapkan untuk ruang vektor.
Berikut adalah matriks 2x2. Ini adalah contoh dari pemetaan geser.
Matriks digunakan dalam banyak tujuan yang berbeda. Mereka banyak digunakan dalam grafis 2D dan 3D.
Font italic juga contoh dari
pemetaan geser!
Salah satu cara yang digunakan adalah matriks untuk melakukan transformasi linear.
Jika anda pernah menggunakan transformasi di Photoshop, anda akan melihat aljabar linear dalam operasi tersebut.
Hal ini merupakan hasil dari penerapan matriks 2D di atas untuk satu set piksel dalam ruang vektor. Matriks selalu diterapkan pada ruang vektor.
Apakah yang dimaksud dengan vektor eigen?
Ketika kita menerapkan matriks untuk satu set piksel, itu semua skala dari pixel ke kanan dengan faktor 1,25. Perhatikan bahwa hubungan horizontal piksel tidak berubah sama sekali atau dengan kata lain gambar akan diskala dengan 1,25 sepanjang sumbu-x dan meninggalkan sama di sumbu y.
Vektor Eigen adalah vektor-vektor dalam ruang bahwa ketika ditindak lanjuti oleh matriks hanya besarnya mereka terpengaruh, dan tidak ke arah mereka. Sekali lagi dalam hal piksel, hubungan antara piksel tidak terpengaruh dalam arah horisontal, tetapi segala arah.
Secara teknis, vektor eigen adalah vektor yang memenuhi persamaan
Ax = λx
Bagaimana kita menghitung vektor eigen?
Ada beberapa pendekatan yang dapat kita gunakan untuk memecahkan untuk dicari setelah vektor eigen dari matriks kita. Ada yang lebih akurat, ada yang lebih cepat, beberapa akan menemukan vektor eigen yang lebih dari yang lain.
Kali ini kita hanya mencari vektor eigen yang terkait dengan nilai eigen dominan. Kita tidak perlu tahu tentang salah satu vektor eigen unit lain. Kita ingin menemukan vektor eigen secepat mungkin.
Power Iteration
Metode power iteration adalah algoritma sederhana namun kuat.
- Kita mulai dengan vektor. Hal ini dapat menggunakan vektor apapun dengan setidaknya satu elemen tidak nol.
- Kita mengalikan vektor ini dengan matriks.
- Kita mengambil vektor yang dihasilkan, menormalkan, dan kemudian kalikan dengan matriks lagi.
- Kita ulangi langkah 3 sampai kita mencapai jumlah yang diterima toleransi untuk kesalahan.
- Vektor yang dihasilkan adalah pendekatan dari vektor eigen yang kita cari.
Hal ini tampak sederhana, tetapi dapat kita lihat bagaimana kaitannya dengan konsep kita tentang vektor eigen.
Apa yang di representasikan oleh vektor ini? Mereka mewakili kemungkinan berada di sebuah halaman web dan berakhir di halaman web lain. Mengapa? Karena itulah bagaimana kita mengatur segalanya. Kita mulai dengan deskripsi jaringan website/blog. Kita membuat grafik yang menghubungkan diantaranya. Kita kemudian mengubah bahwa grafik untuk mewakili probabilitas mengklik link secara acak. Kita sekarang mengambil bahwa seluruh struktur dan sekaligus mencari tahu di mana ia menunjuk.
Mengapa kita ingin menormalkan vektor kita? Kita ingin mereka menambahkan hingga 1 sehingga kita dapat komunikasi dengan mereka sebagai pecahan dari satu keseluruhan, sesuatu yang cenderung kita temukan.
Bagaimana kita menormalkan vektor?
Sebuah vektor ternormalisasi jika vektor yang dibagi dengan panjangnya menciptakan vektor satuan. Ini bisa dikatakan bahwa semua elemen dalam vektor menambahkan hingga 1.
Vector.prototype.normalize = function() {
var row_length = this.elements.length;
var t = 0;
for (var i = 0; i < row_length; i++) {
t += this.elements[i];
}
return this.multiply((1.0/t));
}
Mengapa menggunakan power iteration?
Metode power iteration hanya akan menemukan vektor eigen yang terkait dengan nilai eigen terbesar secara absolut. Selain itu, akan gagal jika matriks tersebut cukup jarang. Untungnya, istilah-istilah tersebut sesuai dengan kebutuhan kita saat ini dengan sempurna. Dibandingkan dengan eigensolvers lain, metode daya komputasi kurang intensif daripada melakukan dekomposisi penuh.
Berikut kodenya:
Matrix.prototype.eigenvector = function() {
var tolerance = 0.000001;
var row_length = this.elements[0].length;
var a = [];
for (var i = 0; i < row_length; i++) {
a.push(1);
}
var x = $V(a);
var c_old = 0;
for (var i = 0; i < 100; i++) {
var x_new = x.normalize()
var c_new = x_new.elements[0];
var e = 100 * (c_new - c_old)/c_new;
if (Math.abs(e) < tolerance) {
break;
}
x = this.multiply(x_new);
c_old = c_new;
}
return $V(x);
}
Kode yang terakhir, ini merupakan persamaan yang akan membawa semua langkah yang terpisah menjadi satu:
Matrix.prototype.pagerank = function() {
var damping_value = Pages.dampingFactor;
var row_stochastic_matrix = this.row_stochastic(damping_value);
var transposed_matrix = row_stochastic_matrix.transpose();
var eigenvector = transposed_matrix.eigenvector();
var normalized_eigenvector = eigenvector.normalize();
return normalized_eigenvector.elements;
Saya rasa penjelasan dalam membuat program untuk mencari nilai google pagerank sudah cukup.
Di bawah ini saya akan memberikan link untuk mendownload contoh programnya dan bisa digunakan supaya anda lebih mengerti kembali penjelasan dari metode yang digunakan.
Semoga bermanfaat.
