Algoritma PageRank dan HITS

PageRank dan HITS adalah algoritma analisis tautan yang memperkirakan kepentingan atau otoritas halaman web dari struktur grafik hyperlink, bukan hanya dari konten halaman.

Definition

PageRank menetapkan setiap halaman skor kepentingan yang independen terhadap kueri, yang sama dengan probabilitas stasionernya di bawah peselancar acak yang mengikuti tautan keluar dengan probabilitas peredaman dan melakukan teleportasi jika tidak, sementara HITS menghitung, untuk subgraf yang bergantung pada kueri, skor otoritas untuk halaman dengan konten berharga dan skor hub untuk halaman yang menautkan ke otoritas yang baik, yang masing-masing saling menguatkan.

Scope

Topik ini mencakup dua algoritma analisis tautan fundamental: PageRank, ukuran kepentingan halaman yang independen terhadap kueri berdasarkan model peselancar acak dengan teleportasi, dan HITS, skema yang bergantung pada kueri yang menghitung skor hub dan otoritas yang saling menguatkan. Ini membahas formulasi random-walk dan eigenvector yang mendasarinya, peran peredaman dan teleportasi, konvergensi, dan varian yang sensitif terhadap topik. Ini tidak mencakup bagaimana skor-skor ini digabungkan dengan fitur teks ke dalam peringkat akhir, yang termasuk dalam peringkat pencarian web.

Core questions

• Bagaimana model peselancar acak mendefinisikan PageRank sebagai distribusi stasioner?
• Mengapa faktor peredaman atau teleportasi diperlukan agar PageRank terdefinisi dengan baik?
• Bagaimana skor hub dan otoritas dalam HITS saling menguatkan?
• Bagaimana skor-skor ini dihitung secara iteratif, dan kapan skor-skor ini konvergen?
• Bagaimana PageRank dan HITS berbeda dalam hal independen terhadap kueri versus bergantung pada kueri?

Key concepts

• PageRank
• model peselancar acak
• faktor peredaman dan teleportasi
• distribusi stasioner / eigenvector utama
• HITS
• hub dan otoritas
• penilaian independen kueri vs. bergantung kueri
• iterasi daya dan konvergensi

Key theories

Model peselancar acak PageRank

Memodelkan peselancar yang mengikuti tautan dengan probabilitas yang sama dengan faktor peredaman dan jika tidak melompat ke halaman acak menghasilkan rantai Markov yang distribusi stasioner uniknya menilai halaman berdasarkan kunjungan jangka panjang, memberikan ukuran kepentingan yang stabil dan independen terhadap kueri.

Hub dan otoritas HITS

Dalam subgraf yang berfokus pada kueri, HITS menetapkan setiap halaman skor otoritas yang proporsional dengan skor hub halaman yang menautkannya dan skor hub yang proporsional dengan skor otoritas halaman yang ditautkannya, dihitung dengan mengulang hubungan yang saling menguatkan ini hingga konvergensi.

Clinical relevance

PageRank sangat penting bagi munculnya pencarian web skala besar dan tetap menjadi titik acuan konseptual untuk kepentingan dan otoritas pada grafik. Ide-ide analisis tautan dapat digeneralisasikan di luar web ke jaringan kutipan, pengaruh jejaring sosial, deteksi penipuan, dan rekomendasi, di mana pun tautan seperti dukungan membawa informasi.

History

Pada tahun 1998 dan 1999, dua proposal yang hampir bersamaan menunjukkan bahwa hyperlink mengkodekan otoritas: HITS dari Kleinberg dan PageRank dari Page dan Brin. Skor PageRank yang independen terhadap kueri dan dihitung secara global terbukti sangat cocok untuk penyajian skala web dan menjadi dasar mesin pencari terkemuka, sementara HITS memengaruhi distilasi topik dan penelitian peringkat grafik selanjutnya.

Key figures

• Larry Page
• Sergey Brin
• Jon Kleinberg
• Rajeev Motwani

Seminal works

• page1999
• kleinberg1999
• brin1998

Frequently asked questions

Apa perbedaan antara PageRank dan HITS?

PageRank menghitung satu skor kepentingan yang independen terhadap kueri untuk setiap halaman dari seluruh grafik web sebelumnya, sedangkan HITS menghitung skor hub dan otoritas yang bergantung pada kueri pada subgraf kecil yang dibangun di sekitar kueri pada waktu pengambilan. PageRank lebih mudah diskalakan untuk penyajian web.

Mengapa PageRank membutuhkan faktor peredaman?

Tanpa itu, peselancar acak dapat terjebak dalam halaman tanpa tautan keluar atau dalam siklus, dan distribusi stasioner mungkin tidak unik atau terdefinisi dengan baik. Probabilitas peredaman (teleportasi) memungkinkan peselancar sesekali melompat ke halaman acak, menjamin skor yang unik dan berperilaku baik.