Perayapan Web dan Struktur Tautan

Perayapan web adalah proses otomatis untuk menemukan dan mengunduh halaman web dengan mengikuti hyperlink, dan struktur tautan yang dihasilkan membentuk grafik yang dilalui dan dianalisis oleh sistem pencarian.

Definition

Perayapan web adalah penelusuran algoritmik web yang dimulai dari URL awal (seed URLs) dan berulang kali mengambil halaman serta mengekstrak tautan keluarannya untuk menemukan lebih banyak halaman, sedangkan struktur tautan mengacu pada grafik berarah yang dibentuk oleh halaman dan hyperlink di antaranya.

Scope

Topik ini mencakup bagaimana perayap secara sistematis mengambil halaman web dan bagaimana grafik hyperlink web terstruktur. Ini membahas arsitektur perayap, batas URL (URL frontier) dan batasan kesopanan (politeness constraints), deteksi duplikat dan hampir duplikat, kesegaran dan penjadwalan perayapan ulang, serta penghormatan terhadap pengecualian robot (robots exclusion). Ini juga mencakup properti empiris dari grafik web, seperti struktur dasi kupu-kupu (bowtie) yang luas dan distribusi derajat berekor panjang (heavy-tailed degree distribution), yang menginformasikan perayapan dan analisis tautan. Ini tidak termasuk penggunaan tautan untuk peringkat, yang dibahas di bawah PageRank dan HITS.

Core questions

• Bagaimana perayap menemukan, memprioritaskan, dan menjadwalkan halaman yang diambilnya?
• Bagaimana kesopanan, pengecualian robot, dan beban server dihormati selama perayapan?
• Bagaimana halaman duplikat dan hampir duplikat dideteksi dan ditangani?
• Bagaimana kesegaran perayapan dipertahankan seiring perubahan halaman?
• Struktur berskala besar apa yang ditunjukkan oleh grafik web?

Key concepts

• perayap web / laba-laba (spider)
• batas URL (URL frontier) dan kumpulan awal (seed set)
• kesopanan perayapan (crawl politeness) dan robots.txt
• deteksi duplikat dan hampir duplikat
• kesegaran dan penjadwalan perayapan ulang
• grafik web
• struktur dasi kupu-kupu (bowtie structure)
• distribusi derajat masuk (in-degree) dan derajat keluar (out-degree)

Key theories

Arsitektur perayap dan batas URL (URL frontier)

Perayap mempertahankan batas URL yang akan diambil, menerapkan kebijakan prioritas dan kesopanan, mengurai halaman yang diambil untuk mengekstrak tautan baru, dan melacak halaman yang telah dikunjungi, menyeimbangkan cakupan, kesegaran, dan batasan sumber daya.

Struktur grafik web makroskopik

Studi empiris menunjukkan grafik tautan web memiliki bentuk dasi kupu-kupu yang khas dengan inti yang terhubung kuat (strongly connected core) yang besar ditambah komponen masuk (in component) dan keluar (out component), serta derajat masuk berekor panjang (heavy-tailed in-degree), yang membatasi keterjangkauan dan menginformasikan strategi perayapan.

Clinical relevance

Perayapan adalah tahap akuisisi data dari setiap mesin pencari web dan analitik web berskala besar, pengarsipan, serta konstruksi kumpulan data. Pemahaman struktur tautan memandu perayapan yang efisien, membantu memperkirakan cakupan, dan mendasari ukuran otoritas berbasis tautan yang digunakan dalam peringkat.

History

Perayap web muncul bersamaan dengan web awal pada pertengahan 1990-an untuk mengisi indeks pencarian. Cho dan rekan-rekannya mempelajari perayapan yang efisien dan pengurutan URL pada tahun 1998, dan studi 'struktur grafik di web' tahun 2000 mengungkapkan makrostruktur dasi kupu-kupu web. Seiring pertumbuhan web, perayapan berkembang menjadi disiplin sistem terdistribusi berskala besar yang menekankan kesegaran, cakupan, dan kesopanan.

Key figures

• Andrei Broder
• Prabhakar Raghavan
• Junghoo Cho
• Hector García-Molina

Seminal works

• broder2000
• cho1998
• manning2008

Frequently asked questions

Apa itu batas URL (URL frontier) dalam perayap?

Batas URL adalah antrean URL yang ditemukan tetapi belum diambil. Perayap berulang kali memilih URL dari batas sesuai dengan kebijakan prioritas dan kesopanan, mengambil halaman, mengekstrak tautan baru, dan menambahkan URL yang belum pernah terlihat sebelumnya kembali ke batas.

Apa arti struktur 'dasi kupu-kupu' (bowtie) dari web?

Studi berskala besar menemukan bahwa grafik web memiliki inti yang terhubung kuat yang besar, komponen 'masuk' dari halaman yang dapat mencapai inti, komponen 'keluar' yang dapat dijangkau darinya, ditambah sulur (tendrils) dan bagian yang terputus, menyerupai dasi kupu-kupu. Bentuk ini memengaruhi halaman mana yang dapat dijangkau oleh perayap dari URL awal tertentu.