Faktor yang mempengaruhi PageRank

image from google

PageRank teori menyatakan bahwa surfer imajiner yang secara acak mengklik link pada akhirnya akan berhenti mengklik. Probabilitas, pada langkah apapun, bahwa orang akan terus merupakan faktor redaman d . Berbagai penelitian telah menguji faktor redaman yang berbeda, tetapi umumnya diasumsikan bahwa faktor redaman akan ditetapkan sekitar 0,85.5

Faktor redaman dikurangi dari 1 (dan dalam beberapa variasi dari algoritma, hasilnya dibagi dengan jumlah dokumen ( N ) dalam koleksi) dan istilah ini kemudian ditambahkan ke produk dari faktor redaman dan jumlah dari skor PageRank masuk. Itu adalah,

$PR (A) = {1 - d \ over N} + d \ left (\ frac {PR (B)} {L (B)} + \ frac {PR (C)} {L (C)} + \ frac {PR (D)} {L (D)} + \, \ cdots \ kanan).$

Jadi PageRank setiap halaman berasal sebagian besar dari PageRanks halaman lainnya. Faktor redaman menyesuaikan nilai yang diperoleh ke bawah. Kertas asli, bagaimanapun, memberikan rumus berikut, yang telah menyebabkan beberapa kebingungan:

$PR (A) = 1 - d + d \ left (\ frac {PR (B)} {L (B)} + \ frac {PR (C)} {L (C)} + \ frac {PR (D) } {L (D)} + \, \ cdots \ kanan).$

Perbedaan antara mereka adalah bahwa nilai-nilai PageRank dalam rumus jumlah pertama yang satu, sedangkan pada susu formula kedua setiap PageRank dikalikan dengan N dan jumlahnya menjadi N . Sebuah pernyataan di Page dan Brin kertas bahwa "jumlah semua PageRanks adalah salah satu" 5 dan klaim oleh karyawan Google lainnya 21 mendukung varian pertama dari rumus di atas.

Page dan Brin bingung dua formula dalam makalah mereka yang paling populer "The Anatomy of a Large-Scale Hypertextual Web Search Engine", di mana mereka keliru mengklaim bahwa formula yang terakhir membentuk distribusi probabilitas atas halaman web.

Google kalkulasi ulang nilai PageRank setiap kali menjelajah Web dan membangun kembali indeks. Seperti Google meningkatkan jumlah dokumen dalam koleksi, perkiraan awal PageRank menurun untuk semua dokumen.

Rumus menggunakan model dari surfer acak yang bosan setelah beberapa klik dan switch ke halaman acak. Nilai PageRank halaman mencerminkan kemungkinan bahwa surfer acak akan mendarat di halaman tersebut dengan mengklik link. Hal ini dapat dipahami sebagairantai Markov di mana negara adalah halaman, dan transisi, yang semua sama-sama mungkin, adalah hubungan antara halaman.

Jika halaman yang tidak memiliki link ke halaman lain, menjadi tenggelam dan karena itu mengakhiri proses berselancar acak. Jika surfer acak tiba di halaman wastafel, itu mengambil lain URL secara acak dan terus berselancar lagi.

Saat menghitung PageRank, halaman tanpa link keluar diasumsikan link ke semua halaman lain dalam koleksi. Oleh karena itu, nilai PageRank mereka dibagi secara merata di antara semua halaman lainnya. Dengan kata lain, untuk menjadi adil dengan halaman yang tidak tenggelam, acak transisi ini ditambahkan ke semua node di Web, dengan probabilitas sisa biasanya digunakan untuk d = 0,85, diperkirakan dari frekuensi bahwa surfer rata-rata menggunakan nya atau browser-nya fitur bookmark.

Jadi, persamaan adalah sebagai berikut:

$PR (p_i) = \ frac {1-d} {N} + d \ sum_ {p_j \ di M (p_i)} \ frac {PR (p_j)} {L (p_j)}$

di mana

adalah halaman dalam pertimbangan, M (p_i)

adalah set halaman yang memiliki pranala ke p_i

adalah jumlah link keluar pada halaman p_j

, dan Nadalah jumlah total halaman.

Nilai PageRank adalah entri dari kiri yang dominan eigenvector dari dimodifikasi matriks adjacency . Hal ini membuat PageRank metrik sangat elegan: vektor eigen adalah

$\ Mathbf {R} = \ begin {} bmatrix PR (p_1) \\ PR (p_2) \\ \ vdots \\ PR (P_n) \ end {} bmatrix$

di mana R adalah solusi dari persamaan

$\ Mathbf {R} = \ begin {} {bmatrix (1-d) / N} \\ {(1-d) / N} \\ \ vdots \\ {(1-d) / N} \ end {bmatrix } + d \ begin {} bmatrix \ ela (p_1, p_1) & \ ela (p_1, p_2) & \ cdots & \ ela (p_1, P_n) \\ \ ela (p_2, p_1) & \ ddots & & \ vdots \\ \ vdots & & \ ela (p_i, p_j) & \\ \ ela (P_n, p_1) & \ cdots & & \ ela (P_n, P_n) \ end {} bmatrix \ mathbf {R}$

di mana fungsi adjacency $\ Elo (p_i, p_j)$ adalah 0 jika halaman p_j

tidak terhubung ke p_i

, dan normalisasi sehingga, untuk setiap j

$\ Sum_ {i = 1} ^ N \ ela (p_i, p_j) = 1$ .

yaitu unsur-unsur setiap kolom jumlah sampai dengan 1, sehingga matriks adalah matriks stokastik (untuk lebih jelasnya lihat perhitungan bagian bawah). Jadi ini adalah varian darivektor eigen sentralitas ukuran umum digunakan di analisis jaringan .

Karena eigengap besar matriks adjacency dimodifikasi di atas, nilai-nilai PageRank eigenvector dapat didekati untuk dalam tingkat akurasi yang tinggi dalam hanya beberapa iterasi.

Sebagai hasil dari teori Markov , dapat ditunjukkan bahwa PageRank dari halaman yang kemungkinan tiba di halaman yang setelah sejumlah besar klik. Hal ini terjadi untuk sama $t ^ {- 1}$ di mana

adalah harapan dari jumlah klik (atau melompat acak) diperlukan untuk mendapatkan dari halaman kembali ke dirinya sendiri.

Salah satu kelemahan utama PageRank adalah bahwa hal itu nikmat halaman yang lebih tua. Sebuah halaman baru, bahkan yang sangat baik, tidak akan memiliki banyak link kecuali itu adalah bagian dari situs yang ada (situs menjadi padat terhubung set halaman, sepertiWikipedia ).

Beberapa strategi telah diusulkan untuk mempercepat perhitungan PageRank.

Berbagai strategi untuk memanipulasi PageRank telah digunakan dalam upaya bersama untuk meningkatkan hasil pencarian peringkat dan menguangkan link iklan. Strategi ini telah sangat mempengaruhi keandalan konsep PageRank, [ rujukan? ] yang dimaksudkan untuk menentukan dokumen yang benar-benar sangat dihargai oleh masyarakat Web.

Sejak Desember 2007, ketika mulai aktif situs menghukum menjual link teks dibayar, Google telah dilawan koleksi link dan skema lain yang dirancang untuk artifisial mengembang PageRank. Bagaimana Google mengidentifikasi koleksi link dan alat PageRank manipulasi lainnya adalah antara Google rahasia dagang .

PageRank dapat dihitung baik iteratif atau aljabar. Metode iterasi dapat dilihat sebagai iterasi daya metode 24 25 atau metode listrik. Operasi matematika dasar yang dilakukan adalah identik.

Pada

, distribusi probabilitas awal diasumsikan, biasanya

$PR (p_i; 0) = \ frac {1} {N}$ .

Pada setiap langkah waktu, perhitungan, seperti yang dijelaskan di atas, hasil

$PR (p_i; t + 1) = \ frac {1-d} {N} + d \ sum_ {p_j \ di M (p_i)} \ frac {PR (p_j; t)} {L (p_j)}$ .

atau dalam notasi matriks

$\ Mathbf {R} (t + 1) = d \ mathcal {M} \ mathbf {R} (t) + \ frac {1-d} {N} \ mathbf {1}$ , (*)

di mana $\ Mathbf {R} _i (t) = PR (p_i; t)$ dan $\ Mathbf {1}$ adalah vektor kolom panjang

yang berisi satu-satunya.

Matriks $\ Mathcal {M}$ didefinisikan sebagai

$\ Mathcal {M} _ {ij} = \ begin {} 1 kasus / L (p_j), & \ mbox {jika} j \ mbox {} link ke i \ \\ 0, & \ mbox {jika} \ end { kasus}$

yaitu,

$\ Mathcal {M}: = (K ^ {- 1} A) ^ T$ .

di mana

menunjukkan matriks adjacency dari grafik dan

adalah matriks diagonal dengan outdegrees di diagonal.

Perhitungan berakhir ketika untuk beberapa kecil $\ Epsilon$

$| \ Mathbf {R} (t + 1) - \ mathbf {R} (t) | <\ epsilon$ .

yaitu, ketika konvergensi diasumsikan.

Aljabar pada Pagerank

Untuk $t \ ke \ infty$ (yaitu, dalam kondisi mapan ), persamaan di atas (*) berbunyi

$\ Mathbf {R} = d \ mathcal {M} \ mathbf {R} + \ frac {1-d} {N} \ mathbf {1}$ . (**)

Solusinya diberikan oleh

$\ Mathbf {R} = (\ mathbf {I} -d \ mathcal {M}) ^ {- 1} \ frac {1-d} {N} \ mathbf {1}$ .

dengan matriks identitas $\ Mathbf {I}$ .

Solusinya ada dan unik untuk 0 <d <1

. Hal ini dapat dilihat dengan memperhatikan bahwa $\ Mathcal {M}$ adalah dengan konstruksi matriks stokastik dan karenanya memiliki nilai eigen sama dengan satu sebagai konsekuensi dari teorema Perron Frobenius- .

Faktor yang mempengaruhi PageRank

Related : Faktor yang mempengaruhi PageRank

Popular Posts

Labels

Total Tayangan Laman

Arsip