Web Tarama ve Bağlantı Yapısı
Web tarama, köprüleri (hyperlink) takip ederek web sayfalarını keşfetme ve indirme sürecinin otomatikleştirilmiş halidir; ortaya çıkan bağlantı yapısı ise arama sistemlerinin hem gezindiği hem de analiz ettiği bir grafik oluşturmaktadır.
Tanım
Web tarama, başlangıç (seed) URL'lerinden başlayarak web'in algoritmik olarak gezilmesidir; bu süreçte sayfalar tekrar tekrar getirilir ve daha fazla sayfa keşfetmek için giden bağlantıları çıkarılırken, bağlantı yapısı ise sayfalar ve aralarındaki köprüler (hyperlink) tarafından oluşturulan yönlendirilmiş grafiği ifade etmektedir.
Kapsam
Bu konu, tarayıcıların web sayfalarını sistematik olarak nasıl getirdiğini ve web'in köprü grafiğinin nasıl yapılandığını kapsamaktadır. Tarayıcı mimarisi, URL sınırı (URL frontier) ve nezaket kısıtlamaları, yinelenen ve neredeyse yinelenen içerik tespiti, tazelik ve yeniden tarama planlaması ile robots dışlama kurallarına uyumu ele almaktadır. Ayrıca, web grafiğinin geniş 'papyon' yapısı (bowtie structure) ve ağır kuyruklu derece dağılımı gibi ampirik özelliklerini de içermekte olup, bunlar hem tarama hem de bağlantı analizine bilgi sağlamaktadır. Konu, PageRank ve HITS başlıkları altında ele alınan bağlantıların sıralama amaçlı kullanımını dışlamaktadır.
Temel sorular
- Bir tarayıcı, getireceği sayfaları nasıl keşfeder, önceliklendirir ve planlar?
- Tarama sırasında nezaket, robots dışlama kuralları ve sunucu yükü nasıl gözetilir?
- Yinelenen ve neredeyse yinelenen sayfalar nasıl tespit edilir ve ele alınır?
- Sayfalar değiştikçe tarama tazeliği nasıl korunur?
- Web grafiği hangi büyük ölçekli yapıyı sergilemektedir?
Anahtar kavramlar
- web tarayıcısı / örümcek (spider)
- URL sınırı (URL frontier) ve başlangıç kümesi (seed set)
- tarama nezaketi ve robots.txt
- yinelenen ve neredeyse yinelenen içerik tespiti
- tazelik ve yeniden tarama planlaması
- web grafiği
- 'papyon' yapısı (bowtie structure)
- içeriye ve dışarıya doğru derece dağılımları (in-degree and out-degree distributions)
Temel kuramlar
- Tarayıcı mimarisi ve URL sınırı (URL frontier)
- Bir tarayıcı, getirilecek URL'lerden oluşan bir sınır (frontier) tutar, önceliklendirme ve nezaket politikalarını uygular, getirilen sayfaları yeni bağlantıları çıkarmak için ayrıştırır ve ziyaret edilen sayfaları takip ederek kapsam, tazelik ve kaynak sınırlamaları arasında denge kurar.
- Makroskopik web grafik yapısı
- Ampirik çalışmalar, web'in bağlantı grafiğinin büyük, güçlü bir şekilde bağlı çekirdek (strongly connected core) ile içeri ve dışarı bileşenleri (in and out components) ve ağır kuyruklu içeriye doğru derece (heavy-tailed in-degree) ile karakteristik bir 'papyon' şekline (bowtie shape) sahip olduğunu göstermektedir; bu durum erişilebilirliği kısıtlamakta ve tarama stratejisini bilgilendirmektedir.
Klinik önem
Tarama, her web arama motorunun ve büyük ölçekli web analizi, arşivleme ve veri kümesi oluşturma süreçlerinin veri toplama aşamasını oluşturmaktadır. Bağlantı yapısını anlamak, verimli taramaya rehberlik etmekte, kapsamın tahmin edilmesine yardımcı olmakta ve sıralamada kullanılan bağlantı tabanlı yetki ölçütlerinin temelini oluşturmaktadır.
Tarihçe
Web tarayıcıları, arama indekslerini beslemek amacıyla 1990'ların ortalarında erken web ile birlikte ortaya çıkmıştır. Cho ve arkadaşları 1998'de verimli tarama ve URL sıralamasını incelemiş, 2000 yılındaki 'web'deki grafik yapısı' çalışması ise web'in 'papyon' makro yapısını (bowtie macrostructure) ortaya koymuştur. Web büyüdükçe, tarama; tazelik, kapsam ve nezaketi vurgulayan büyük ölçekli dağıtık sistemler disiplinine dönüşerek olgunlaşmıştır.
Öne çıkan isimler
- Andrei Broder
- Prabhakar Raghavan
- Junghoo Cho
- Hector García-Molina
İlgili konular
Temel eserler
- broder2000
- cho1998
- manning2008
Sıkça sorulan sorular
- Bir tarayıcıdaki URL sınırı (URL frontier) nedir?
- URL sınırı (URL frontier), keşfedilmiş ancak henüz getirilmemiş URL'lerin kuyruğudur. Bir tarayıcı, öncelik ve nezaket politikalarına göre sınırdan (frontier) tekrar tekrar URL'ler seçer, sayfaları getirir, yeni bağlantıları çıkarır ve daha önce görülmemiş URL'leri tekrar sınıra (frontier) ekler.
- Web'in 'papyon' yapısı (bowtie structure) ne anlama gelmektedir?
- Büyük ölçekli çalışmalar, web grafiğinin büyük, güçlü bir şekilde bağlı çekirdeğe (strongly connected core), çekirdeğe ulaşabilen sayfaların bir 'içeri' bileşenine (in component), ondan erişilebilen bir 'dışarı' bileşenine (out component) ve ayrıca uzantılara (tendrils) ve bağlantısız kısımlara sahip olduğunu, bir papyonu andırdığını bulmuştur. Bu şekil, bir tarayıcının belirli başlangıç (seed) noktalarından hangi sayfalara ulaşabileceğini etkilemektedir.