PageRank Atıf Değerleri: Web'e Düzen Getirmek

Bir web sayfasının önemi, doğası gereği, okuyucuların ilgi duyduğu konulara, bilgi birikimlerine ve tavırlarına kişisel bakış açısıyla bağlı bir konudur. Fakat Web sayfalarının birbirlerine göre önemleri hakkında daha hala söylenebilecek çok şey bulunmakta. Bu makale, Web sayfalarını tarafsız ve mekanik olarak değerlendiren, etkili bir şekilde insanların ilgi duydukları ve onları ilgilendiren konuları ölçen, PageRank’i tanımlamaktadır.

PageRank’i, ideal, rastgele bir web gezginini referans alarak kıyaslıyoruz. PageRank’in çok sayıda sayfa için nasıl efektif bir şekilde hesaplanacağını gösteriyoruz. Ve, PageRank’in arama ve kullanıcı hareketlerine nasıl uygulanabileceğini gösteriyoruz.

Bu içerik Stanford Üniversitesi tarafından 1998 yılında yayınlanmış olan PageRank makalesinin çevirisidir.

1. Giriş ve Motivasyon

World Wide Web bilginin sağlanması konusunda yeni pek çok meydan okumayı da beraberinde getiriyor. Oldukça büyük ve heterojen. Mevcut hesaplamalar 150 milyonun üstünde web sayfasının olduğunu ve bu sayının bir yıldan daha az bir süre içerisinde ikiye katlandığını gösteriyor. Daha da önemlisi web sayfaları, “Joe bugün öğle yemeğinde ne yiyor”’ dan, bilgi sağlayan gazetelere kadar çok geniş bir dağılım gösteriyorlar. Bu ana meydan okumaya ek olarak, Web’deki arama motorları, deneyimsiz kullanıcılar ve arama motorlarının sıralama fonksiyonlarını manipüle etmek isteyen sayfalarla da baş etmek zorunda.

Bununla birlikte, “düz” dokümanların aksine, World Wide Web, web sitelerinin üst bölümlerindeki tekstler içerisinde, link yapısı ve link teksti gibi önemli ölçüde yardımcı bilgiler de barındıran bir hypertext (yardımlı metin) yapısına sahiptir. Bu makalede, küresel olarak her bir web sayfasının “önem” değerini oluşturmak için Web’in link yapısından faydalandık. PageRank adı verilen bu sıralama, arama motorlarına ve kullanıcılara, World Wide Web’in geniş heterojenliğini çabucak anlamlı kılarak yardımcı oluyor. 

1.1 Web Sayfalarının Çeşitliliği

Her ne kadar akademik atıf analizi ile ilgili hali hazırda geniş bir literatür olsa da, web sayfaları ve akademik yayınlar arasında birkaç önemli fark bulunuyor. Dikkatlice incelenen akademik yayınların aksine, web sayfaları herhangi bir kalite kontrolü veya yayın ücreti olmadan hızla çoğalıyorlar. Basit bir program aracılığıyla, çok fazla sayıda sayfa kolaylıkla üretilebiliyor ve bu sayfalarla atıf sayıları yapay olarak şişirebiliyor. Web, kazanç odaklı rakip girişimcileri bünyesinde bulundurduğu için, arama motoru algoritmalarının hareketlerine karşın stratejiler de zamanla gelişiyor. Bu nedenle, web sitelerinin kopyalanabilir özelliklerine ilişkin geliştirilen stratejiler manipülasyona da müsait. Ek olarak, akademik makaleler iyi tanımlanmış işler ve amaçları açısından olduğu kadar, kalite ve atıf açısından da kabaca benzerler. Web sayfaları akademik makalelerin kalitesine, kullanımına, atfına ve uzunluğuna göre çok daha geniş bir ölçekte çeşitlilik gösteriyorlar. IBM bilgisayar hakkında anlaşılmaz bir sorunun sorulduğu rastgele arşivlenmiş bir mesaj, IBM ana sayfasından oldukça farklıdır. Sürücülerin dikkatini dağıtması noktasında cep telefonu hakkındaki araştırma makalesi ile belirli bir cep telefonu sağlayıcısının reklamı birbirlerinden oldukça farklıdır. Bir kullanıcı tarafından deneyimlenen ortalama web sayfası kalitesi, web sayfasının ortalama kalitesinden daha yüksektir. Bunun nedeni web sayfalarının oluşturulmasının ve yayınlanmasının kolay olmasından kaynaklanır ve bu durum kullanıcıların okumak istemeyecekleri düşük kalitede web siteleri ortaya çıkarır.

Web sayfalarının nasıl birbirlerinden ayrılabileceği ile ilgili çok sayıda yöntem var. Bu makalede, özellikle biri üzerinde duracağız – web sayfalarının toplam göreli önemlerine yönelik bir yaklaşım. 

1.2 Pagerank

Web sayfalarının göreli önemlerini ölçebilmek için, PageRank adı verilen, web sayfalarını, webin genel yapısına göre sıralayan bir hesaplama yöntemi öneriyoruz. PageRank’in arama, tarama ve trafik hesaplamalarına yönelik uygulamaları bulunuyor.

İkinci bölüm PageRank’e yönelik matematiksel bir tanım veriyor ve bazı sezgisel gerekçeler sağlıyor. 3. bölümde, PageRank’i 518 milyon hyperlink için nasıl etkili bir şekilde hesapladığımızı gösteriyoruz. PageRank hizmetinin aramalarda kullanımını test etmek için, Google adı verilen bir web arama motoru oluşturduk. Ayrıca PageRank’in nasıl göz atmaya yönelik(browsing aid) kullanılabileceğini de Bölüm 7.3’de gösterdik.

2. Web’deki Tüm Sayfalar için Sıralama

 
2.1 İlgili Çalışmalar

Akademik atıf analizi ile ilgili çok sayıda çalışma süre gelmiştir [Gar95]. Goffman [Gof71] akademik çevrelerde bilgi akışının nasıl bulaşıcı bir sürece dönüştüğüne ilişkin ilginç bir teori yayınladı.

Web gibi hypertext sistemlerdeki geniş link yapılarından nasıl faydalanabileceğine dair yeterli miktarda çalışma yürütüldü. Pitkow yakın zamanda Ph. D. (doktora), tezini “World Wide Web Ekolojilerinin Karakterize Edilmesi” üzerine, geniş link tabanlı analizler yürüterek tamamladı [Pit97, PPR96]. Weiss link yapısını hesaba katarak küme yöntemlerini [WVS+96] değerlendiriyor. Spertus [Spe97] çeşitli uygulamalar için link yapılarından elde edilebilecek bilgileri tartışıyor [Spe97]. Hypertext yapısına iyi bir görselleştirme beklentisinin eklenmesi, [MFH95, MF95]’de tartışılırdı. Son zamanlarda Kleinberg [Kle98], webin Bağlantılar ve Otoritelere (Hubs and Authorities) göre ilginç bir modelini geliştirdi. Bu model webin ortak-atıf matrisindeki öz vektör hesaplamalarına göre oluşturulmaktadır.

Son olarak, bir kütüphane topluluğu internette neyin “kalite” anlamına geldiğine ilişkin ilgilerini gösterdi [Til] .

Standart atıf analiz tekniklerinin web’in hypertextaul atıf yapısına uygulanmasının denenmesinin gerekliliği açıkça ortada. Her bir linkin bir akademik atıf olduğunu düşünmek mümkün. Bu nedenle büyük bir site olan http://www.yahoo.com/ gibi siteler binlerce backlink (veya atıf) sahibi olacaklar.

Yahoo ana sayfasının çok sayıda backlinkinin olması gerçeği bunun oldukça önemli olduğunu gösteriyor. Gerçekten de, web arama motorlarının çoğu backlink sayısını, veri tabanlarını meyilli hale getirmek, daha yüksek kaliteyi veya daha önemli sayfaları ön plana çıkarma konusunda kullandı. Bununla birlikte, sadece backlink sayısının kullanımı web’de bazı problemlere sahip. Bu problemlerden bazıları, normal akademik atıf veri tabanlarında kendilerini göstermeyen webin kendi karakteriyle ilgili sorunlardır.    

2.2 Web’in Link Yapısı

Her ne kadar hesaplamalar farklılıklar gösterse de, mevcut resim crawlable Web’in 150 milyon düğümü (sayfası) ve 1.7 milyar köşesi (link) olduğunu gösteriyor. Her bir sayfa belirli bir sayda forward linklere (dış köşe) ve backlinklere (iç köşe) sahip (Şekil 1). Belirli bir sayfanın tüm backlinklerini bulup bulmadığımızı hiçbir zaman bilemeyiz, fakat eğer indirirsek, o an için tüm forward linkleri bilebiliriz.

Şekil 1: A ve B, C’ye backlinkdir.

Web sayfaları sahip oldukları backlink sayısına göre değişimler gösterirler. Örneğin, Netscape ana sayfasının 62,804 adet backlinki vardır, mevcut veri tabanımız içerisindeki pek çok sayfanın ise sadece birkaç backlinki bulunmaktadır. Genel olarak, çok fazla sayıda link sahibi olan sayfalar birkaç linke sahip olan sitelere göre “daha önemlidirler”. Atıf sayılarının basit hesaplamalarının gelecek Nobel Ödülü sahiplerinin belirlenmesinde kullanılabileceği spekülasyonu yapıldı [San95]. PageRank atıf hesabının yapılabilmesi için daha sofistike bir yol sunuyor.

PageRank’in pek çok durumda daha ilginç olmasının nedeni, basit atıf hesaplamalarının ortak önem sırası düşüncemizle uyuşmamasıdır. Örneğin, eğer bir web sayfası Yahoo ana sayfasına link vermişse, bu tek bir link olabilir, fakat aynı zamanda çok önemli bir link de olabilir. Bu sayfa belirsiz yerlerden gelen çok sayıda link sayesinde, pek çok sayfadan daha üst sıralarda yer alabilir. PageRank sadece link yapısında “önemin” belirlenmesine yönelik ne kadar iyi bir yaklaşım yapılabileceğinin denenmesinden ibarettir.

2.3 Değerlerin (Rankings), Linkler Aracılığıyla İletimi

Yukarıdaki tartışmayı temel alacak olursak, PageRank’in içsel tanımını yapabiliriz: bir sayfa eğer backlinklerinin toplam değeri yüksekse, yüksek değere sahiptir. Bu durum içerisine, bir web sitesi çok sayıda backlink sahibiyse veya çok yüksek değere sahip birkaç adet linke sahipse durumlarını alır.

2.4 PageRank’in Tanımı

Diyeli ki u bir web sayfası olsun. Ve Fu ise, u’nun yöneldiği sayfa setleri ve Bu da, u’ya yönelen sayfa setleri olsun. Nu = |Fu| u’dan gelen linkler ve c’de normalizasyon için kullanılan bir faktör olsun (bu sayede tüm web sayfalarının toplam değerleri sabittir).

Basit bir değer tanımı olan R ile başlıyoruz. Bu değer PageRank’in bir miktar basitleştirilmiş bir versiyonudur:

Şekil 2: Basitleştirilmiş PageRank Hesabı

Bu, önceki bölümlerdeki öngörüleri formüle döküyor. Bir sayfanın değerinin (rank’inin), link verdiği sayfalara dağıtımı için bu linklerin eşit şekilde bölünerek dağıtıldığını not edelim. Ayrıca c < 1 olduğunu, çünkü forward linke sahip olmayan ve ağırlıklandırmaları sisteme dahil olmayan sayfaların olduğunu da not edelim (bölüm 2.7). Eşitlik tekrarlamalıdır, fakat herhangi bir sıralama seti ile başlayarak ve yeterli sonuca erişene kadar iterasyon yaparak hesaplamanın yapılması mümkündür. Şekil 2 sıra değerlerinin bir grup sayfadan bir diğerine nasıl geçtiğini göstermektedir. Şekil 3 bir sayfa seti için kararlı sabit bir çözümü göstermektedir.

Başka bir şekilde ifade edecek olursak, A’nın kare matris olduğunu ve sıra ve kolanlarının web sayfalarına karşılık geldiğini varsayalım. Eğer u’dan v’ye bir köşe söz varsa, Au,v = 1/Nu dir, eğer yoksa Au,v = 0’dır. Eğer R’yi web sayfaları üzerinden bir vektör olarak ele alırsak, R = cAR olur. Bu durumda R burada c özdeğere sahip A’nın özvektörüdür. Aslında, A’nın baskın özvektörünü istiyoruz. Dejenere olmayan bir başlangıç vektörüyle A’ya arka arkaya uygulanması sayesinde hesaplanabilir.

Bu basitleştirilmiş sıralama fonksiyonunun küçük bir sorunu vardır. İki sayfanın birbirlerine yönlendiklerini fakat başka bir sayfaya yönlenmediğini düşünün. Ve bazı web sayfalarının bunlardan sadece birine yönlendiğini varsayalım. Daha sonra, iterasyon sırasında, bu döngü sıralamayı toplayacaktır fakat değerleri hiç dağıtmayacaktır (dış uçlarının olmaması nedeniyle). Döngü formu batık sıralama (rank sink) adı verilen bir tür tuzaktır.

Batık sıralama sorununun üstesinden gelmek için, bir sıralama skoru tanıttık:

Tanım 1 E(u), değerin kaynağına karşılık gelen Web sayfaları üzerindeki bir vektör olsun. Daha sonra, bir dizi Web sayfasının PageRank’i, RI, aşağıdaki koşulları sağlayan Web sayfalarına bir atamadır.

c’nin maksimum olduğu ve ||RI||1 = 1 (||RI||1 RI’nın L1 normunu gösterir.

Şekil 3: Basitleştirilmiş PageRank Hesaplaması

Şekil 4: Batık Değer Olarak Davranan Döngü

E(u) değerin kaynağına karşılık gelen web sayfaları üzerindeki bir vektördür (Bölüm 6). Eğer E tümüyle pozitifse, c’nin denklemi dengelemek için azaltılması gerektiğini not edelim. Bu durumda, bu teknik bir çürüme faktörüne karşılık gelir. Matris notasyonunda RI = c(ARI + E) olur. ||RI||1 = 1 olduğundan, bunu RI = c(A + E x 1) RI olarak tekrar yazabiliriz. Burada 1 tüm birleri içinde bulunduran vektördür. Bu durumda, RI, (A+E x 1)’in bir özvektörüdür. 

2.5 Rastgele Gezgin Modeli

Yukarıdaki PageRank tanımı, grafiklerdeki rastgele hareketler için başka bir içsel yapıya daha sahiptir. Basitleştirilmiş versiyon, Web grafiğindeki rastgele hareketlerin dağılım olasılığına karşılık gelmektedir. Öngörüsel olarak, “rastgele bir gezginin” hareketinin modellenmesi olarak düşünülebilir. “Rastgele gezgin” arkası arkasına gelen linkleri rastgele şekilde tıklamaya devam edecektir. Bununla birlikte, eğer gerçek bir web gezgini dar bir döngüye sahip web sayfaları ile karşılaşırsa, gezginin döngüde sonsuza kadar devam etmesi olası değildir. Bunun yerine gezgin, başka bir sayfaya geçiş yapacaktır. Ek bir faktör olan E bu davranışı modellemek için bir yol olarak görülebilir: gezgin düzenli olarak “sıkılır” ve E dağılımına bağlı olarak seçilmiş rastgele başka bir sayfaya atlar.

Şimdiye kadar E’yi kullanıcı tanımlı bir parametre olarak tercih ettik. Çoğu testte E’nin alfa değerine sahip tüm web sayfalarında eşit dağılımlı olmasına izin verdik. Bununla birlikte Bölüm 6’da E’nin farklı değerlerinin, nasıl “özelleştirilmiş” sayfa değerleri ürettiğini gösterdik. 

2.6 PageRank’in Hesaplanması

Ölçeklendirme sorunlarını göz ardı edersek PageRank’in hesaplanması oldukça kolaydır. S’nin Web sayfaları üzerindeki herhangi bir vektör olduğunu varsayalım (örneğin E). PageRank aşağıdaki gibi hesaplanabilir:

d faktörünün yakınsama oranını arttırdığını ve ||R||1’i kapsadığını not edelim. Alternatif bir normalizasyon yönteminde R’yi uygun bir faktörle çarpabiliriz. d’nin kullanımı E’ye olan nüfuzunda küçük bir etki yapabilir. 

2.7 Dangling Linkler

Bu modeldeki bir diğer problem de dangling linklerdir. Dangling linkler dışarıya yönelik linke sahip olmayan sayfalara verilen linklerdir. Modeli etkilerler çünkü ağırlıklandırmalarının nereye dağıtılması gerektiği belirsizdir, ve bunlardan çok fazla sayıda vardır. Bu dangling linkler sıklıkla, tüm web’i örneklemek zor olduğu için henüz indirmediğimiz sayfalardır (hali hazırda indirdiğimiz 24 milyon sayfamız bulunuyor, henüz 51 milyon indirilmemiş URL var. Onları tüm PageRank değerleri hesaplanana kadar sistemden çıkarıyoruz). Tüm PageRank’ler hesaplandıktan sonra, bir şeyleri önemli ölçüde etkilemeden, tekrar eklenebiliyorlar. Aynı sayfadaki diğer linklerin normalizasyonunun, bir link kaldırıldığı zaman bir miktar değişeceğini fark edebilirsiniz. Fakat bunun büyük bir etkisinin olmaması gerekir.

3. Uygulama

Stanford WebBase projesinin bir bölümünde [PB98], mevcut 24 milyonluk web sayfası birikimi ile tam bir crawl ve indeks sistemi inşa ettik. Herhangi bir web crawler, URL’lerden oluşan bir veri tabanı tutmak zorundadır, bu sayede web’deki tüm URL’leri keşfedebilir. PageRank’i uygulamak için, web crawler, crawl işlemini yaptıkça bir link indeksi inşa etmelidir. Her ne kadar basit bir işlem olsa da, çok büyük hacimlerin dahil olması nedeniyle belirli bir öneme de sahiptir. Örneğin, mevcut 24 milyon sayfalık veri tabanımızı beş günde indekslemek için, saniyede 50 sayfayı işlemden geçirmemiz gerekmektedir. Her bir sayfada ortalama 11 link yer aldığı için, saniyede 550 linki işlememiz gerekir (neyi link olarak ele aldığınıza da bağlı olarak). Ayrıca, 24 milyon sayfalık veri tabanımız, her bir linkin birbirleriyle kıyaslanması gerektiği 75 milyon tekil URL’ye referans vermektedir.

Karmaşık ve derin bir şekilde kusurlu web yapılarına karşın, sistemin sağlıklı olması için bol miktarda zaman harcandı. Burada sonsuz geniş siteler, sayfalar ve hatta URL’ler bulunmakta. Web sayfalarının önemli bir kısmı düzeltilmemiş HTML’dir ve bu durum ayrıştırıcı tasarımını zorlu hale getirir. Karmaşık deneysel çalışmalar crawling sürecine yardım için kullanılırlar. Örneğin, URL’leri içlerinde /cgi-bin/ ile crawl etmeyiz. Tabi ki “tüm webin” doğru bir örneğini almak sürekli değişim gösterdiği için imkansızdır. Bazı siteler zaman zaman çökebildikleri gibi, bazı kişilerse sitelerinin indekslenmesine izin vermeyebilirler. Tüm bunlara rağmen, biz herkese açık web’in gerçek link yapısının bir temsiline sahip olduğumuzu düşünüyoruz. 

3.1 Pagerank Uygulamaları

Her bir URL’yi eşsiz birer tamsayı veriye dönüştürüyor ve veri tabanındaki her bir hyperlink’i sayfaları tanımlamak için tamsayı ID’leri kullanarak saklıyoruz. Uygulamamamızın detayları [PB98]’de yer alıyor. Genel olarak, PageRank’i şu şekilde tanımlıyoruz: Öncelikle link yapısını Parent ID’ye göre sıralıyoruz. Daha sonra dangling linkleri veri tabanından yukarıda tartıştığımız nedenlerden dolayı ayırıyoruz (birkaç iterasyon dangling linklerin önemli bir kısmını çıkarıyor). Değerlere (ranks), bir başlangıç değer atamamız gerekiyor. Bu atama birkaç stratejiden birisiyle yapılabilir. Eğer yakınsayana kadar iterasyon yapılacaksa, genelde başlangıç değerleri son değerleri etkilemez, sadece yakınsama oranı son değerleri etkiler. Fakat yakınsamayı iyi bir başlangıç değeri seçerek hızlandırabiliriz. Başlangıç değerinin iyi bir şekilde atanması ve küçük, sayılı miktarda iterasyonun uygulanması harika veya gelişmiş performans verebilir.

Hafıza her bir sayfanın ağırlıklandırması için ayrılmıştır. Her biri 4 bayt olan, tek hane duyarlılıklı nokta değerleri kullandığımızdn, bu 75 milyon URL’miz için toplamda  300 megabaytlık bir miktara sahip olmaktadır. Eğer RAM tüm ağırlıklandırmaları kapsamak için yetersiz miktardaysa, çoklu geçişler yapılabilir (bizim uygulamamız yarısı kadar hafıza kullanır ve iki geçiş yapar). Mevcut zaman adımındaki ağırlıklandırmalar hafızada saklanır ve önceki ağırlıklandırmalar disk içerisinde lineer olarak erişilebilirdir. Ayrıca, link veri tabanı A’ya olan tüm erişim, sıralı olması nedeniyle lineerdir. Bu nedenle, A da diskte barındırılabilir. Her ne kadar bu veri yapısı çok geniş olsa da, lineer disk erişimi, her bir iterasyonun tipik bir çalışma istasyonunda 6 dakikada tamamlanmasını sağlar. Ağırlıklandırmalar yakınsandıktan sonra, dangling linkleri tekrar ekler ve daha sonra değerleri tekrar hesaplarız. Dangling linkleri tekrar ekledikten sonra, onları çıkarmak için gerekli olan sayı kadar iterasyon gerçekleştirmemiz gerekir. Diğer türlü, dangling linklerin bir kısmı sıfır ağırlığa sahip olacaktır. Mevcut uygulamada tüm bu süreç toplamda beş saat kadar sürer. Daha katı yakınsama kriterleri, ve daha fazla optimizasyonla, hesaplama çok daha hızlı gerçekleşebilir. Veya, performansı geliştirmek için öz vektörleri daha etkili şekilde hesaplama teknikleri geliştirilebilir. Bununla birlikte, PageRank’in hesaplanması için gerekli olan masraf, tümüyle tekst içeren bir indeks oluşturulması işlemine göre önemsiz seviyededir.

4. Yakınsama Özellikleri

Şekilde 4’teki grafikte de görülebileceği üzere, 322 milyon link barındıran veri tabanındaki PageRank, kabaca 52 itarasyondan oluşan makul bir sayıya yakınsamaktadır. Verinin yarısındaki yakınsama yaklaşık olarak 45 iterasyon sürmektedir. Bu grafik, PageRank’in çok fazla sayıda koleksiyonlar için dahi, ölçeklendirme faktörü log n’ de kabaca lineer olması nedeniyle, iyi ölçekleme sağlayacağını önerir. PageRank hesaplamalarının çok hızlı bir şekilde yakınsıyor olmasındaki ilginç bir alt dalsa, web’in genişleyen-tür de bir grafik olmasıdır. Bunu daha iyi anlayabilmek için, grafiklerdeki rastgele hareketler teorisi ile ilgili kısa bir açıklama verelim; detaylar için Motwani-Raghavan’ın [MR95] makalesini inceleyebilirsiniz. Bir grafikteki rastgele hareketler olasılıkla alakalı süreçlerdir. Herhangi bir zaman aralığında grafiğin belirli bir bölgesinde bulunuruz ve eş dağılımlı olarak rastgele şekilde bir dış ucu, gelecek zaman aralığında ziyaret etmek üzere seçeriz. Her bir S düğümünün alt kümesi alfa çarpı |S|’in bir faktöründen daha büyük olan bir komşuya sahip olduğunda grafiğin bir genişleyici olduğu söylenebilir (dış uçlar yoluyla erişilebilir olan köşeler S’deki düğümlerden yayılmaktadır). Burada alfa genişleme faktörü olarak adlandırılır. Sadece ve sadece en geniş öz değer, ikinci en büyük öz değerden önemli seviyede daha büyük olduğunda, grafik iyi bir genişleme faktörüne sahiptir. Grafikteki rastgele bir hareket, eğer hızlı bir şekilde grafikteki düğüm setlerindeki limit dağılıma yakınsıyorsa, bu durumda onun hızlı-karışan olduğu söylenir (grafikte zaman logaritmik). Ayrıca rastgele hareket grafikte hızlı-karışan bir hareketse bu durumda grafiğin de genişleyen bir grafik veya öz değer ayrımı olan bir grafik olması gerekir.

Tüm bunları PageRank hesaplamalarıyla ilişkilendirmek için, rastgele bir hareketin Web grafiği üzerindeki sınırlayıcı dağılımının belirlenmesinin temel alındığını not edelim. Bir düğümün değerlendirilmesindeki önem, temel olarak rastgele hareketin yeterli miktarda zaman geçtikten sonra düğümde olacağı ile ilgili sınırlayıcı bir olasılıktır. PageRank hesaplamalarının logaritmik zaman ölçeğinde sona ereceği gerçeği, rastgele hareketin hızlı bir şekilde karışıyor olduğunu veya altında yatan grafiğin iyi bir genişleme faktörü olduğunu söylemektir. Genişleyici grafiklerin, Web grafiklerinin hesaplamalarını da dahil eden, gelecekte ortaya çıkarabileceğimiz pek çok tercih edilen özelliği de vardır.

Şekil 5: Yarı Boyutlu ve Tam Boyutlu Link Veri Tabanları için Yakınsama Oranları

5. PageRank ile Arama

PageRank’in en önemli uygulamalarından birisi aramadır. PageRank’i uygulayan iki arama motoruna sahibiz. İlkinde basit başlığa sahip arama motorunu tartışacağız. İkincisi ise Google [BP] adı verilen tümüyle tekstten oluşan bir arama motorudur. Google arama sonuçlarını sıralamak için aralarında IR ölçümleri, yakınlık, anchor text (web sayfalarına yönlenen tekst linkler) ve PageRank değerleri de bulunan birkaç faktörü kullanıyor. Her ne kadar PageRank’in faydalarına ilişkin geniş kapsamlı bir kullanıcı çalışması bu makalenin kapsamının dışında kalsa da, bu makalede bazı örnek sonuçlarla birlikte, karşılaştırmalı deneyleri sunuyoruz.

PageRank’in en önemli faydası eksik belirtilmiş sorgulara yöneliktir. Örneğin, “Stanford University” sorgusu standart bir arama motorunda, Stanford’dan bahseden (yayın listesi gibi) birkaç web sayfası döndürebileceği gibi, PageRank kullanımı sayesinde, ilk önce üniversitenin ana sayfası listelenmektedir. 

5.1 Başlık(Title) Arama

PageRank’in kullanışlılığını test etmek için sadece 16 milyon web sayfasının başlığı bilgisini kullanan bir arama motoru geliştirdik. Sorguya cevap verebilmek için, arama motoru sorgu kelimelerinin tümünü içeren başlıklara sahip olan anahtar kelimeleri buluyor. Daha sonra sonuçları PageRank’e göre sıralıyor. Bu arama motoru oldukça basit ve uygulaması ucuz bir arama motoru. Resmi olmayan testlerde, çok başarılı sonuçlar verdi. Şekil 6’da görülebileceği üzere, “Üniversite” için yapılan bir arama en iyi üniversitelerin listesini veriyor. Bu şekil, kullanıcılara bir seferde iki arama motorunda arama yapmasına izin veren bizim MultiQuery (ÇokluSorgu) sistemimizdir. Soldaki arama motoru PageRank temelli başlık arama motorumuzdur. Çubuk grafikleri ve gösterilen yüzdeler gerçek PageRank değerleridir ve bu değerlerin en üst noktaları %100’e normalize edilmiştir. Bu yüzdenin makalenin herhangi bir başka yerinde kullanılmadığını söyleyebiliriz. Sağdaki arama motoru ise Altavista’dır. Altavista’nın “University” sorgusuna karşılık bu kelimeyle eşleşen rastgele sonuçlar ve serverların ana sayfalarını döndürdüğünü görebilirsiniz. (Altavista kalite göstergesi olarak URL uzunluğunu kullanıyor gibi görünüyor).

Şekil 6: “Üniversite” sorgusunun karşılaştırılması

Tablo 1: En Yüksek Sayfa Değerleri: Temmuz 1996 

5.2 Değer Birleştirme

Başlık(Title) tabanlı PageRank sisteminin çok iyi şekilde çalışması, başlık eşleşmelerinin yüksek seviyede duyarlı olması ve PageRank’in yüksek kaliteyi garanti etmesidir. Web’de “Üniversite” gibi bir sorguda eşleştirme yaparken, anımsatma çok önemli değil çünkü bir kullanıcı bundan çok daha fazlasına bakabilir. Anımsatmanın daha önemli olduğu spesifik aramalarda ise, geleneksel tüm-tekst bilgisi üzerinden skor belirlenmeli ve PageRank birleştirilmelidir. Bizim Google sistemimiz bu tip rank merging (değer birleştirme) işlemini gerçekleştiriyor. Değer birleştirme oldukça zor bir problem olarak bilinir ve bu tip sorgulara yönelik mantıklı bir değerlendirme yapma şansını yakalamadan önce hatırı sayılır miktarda çaba göstermemiz gerekir. Bununla birlikte, bu sorgularda PageRank’i faktör olarak kullanmanın oldukça faydalı olduğunu düşünüyoruz. 

5.3 Örnek Sonuçlar

PageRank’i kullanan tamamıyla tekstten oluşan arama motoru Google’la yeterli miktarda deney yaptık. Her ne kadar geniş ölçekli bir kullanıcı çalışması bu makalenin içeriğinin çok daha üstünde olsa da, Ek A’da örnek bir sorgu sunuyoruz. Daha fazla sorgu için, okuyucuların Google’ı kendilerinin test etmesini öneriyoruz [BP].

Tablo 1 PageRank baz alınarak en üst sırada yer alan ilk 15 sayfayı gösteriyor. Bu listeleme Temmuz 1996’da üretildi. PageRank’in daha yeni tarihli bir hesaplamasında ise, Microsotf PageRank değeri açısından, Netscape’i kıl payıyla geçiyor. 

5.4 Ortak Durumlar

PageRank’in tasarım hedeflerinden birisi ise sorgulardaki ortak durumların ele alınmasıydı. Örneğin, “wolverine” şeklindeki bir kullanıcı sorgusunda, Michigan üniversitende tüm yönetici fonksiyonlarının yürütüldüğü sistemin öğrenciler tarafından içinde wolverine olacak şekilde isimlendirildiğini hatırlayalım. Bizim PageRank temelli başlık arama sistemimiz, “Wolverine Access”’i ilk sonuç olarak döndürmektedir. Bu öğrencilerin tümünün düzenli olarak sorguyu Wolverine Access system olarak gerçekleştirdiği ve rastgele bir kullanıcı ise sorguya “wolverine” yazacağı için oldukça mantıklıdır. Sayfanın HTML’inde yer almadığı için Wolverine Access sitesi güzel bir ortak durumdur. Bu formda Meta-bilgilerinin tanımlanması için iyi bir yol olsaydı dahi, bu yol sorunlu bir yol olurdu çünkü sayfa yazarı bu tür bir değişimde güvenilir olmazdı. Çok sayıda web sayfası yazarı, sayfalarının en iyisi olduğunu ve web’de en fazla kullanılan olduğunu iddia ederdi.

Wolverin’ler hakkında içerisinde bol miktarda bilgi bulunduran bir siteyi bulmanın, wolverine ortak durumlarına sahip siteyi bulma işinden çok daha zor olduğunu not etmemiz gerekiyor. Bir konuyu detaylı şekilde tartışan siteleri bulmak için, tekst eşleşme skorunu webin link yapısı aracılığıyla yayan ilginç bir sistem bulunmakta [Mar97]. Bu sistem daha sonra sayfaları en merkezi rotayı kullanarak döndürmeyi deniyor. Bu sonuç “çiçek” gibi sorgularda iyi sonuç veriyor; sistem içeriğinde çiçekler hakkında detaylı şekilde açıklamalar yapan alt sayfaları döndürecektir. Bu seçenek ortak durum yaklaşımında olduğu gibi ortak kullanımı olan ve reklam içeren bir siteyi döndürmek yerine nasıl çiçek alınır ile ilgili bilgi içeren bir siteyi getirecektir. Bizim görüşümüze göre, bu görevlerden her ikisi de önemlidir ve genel görüşe göre arama motorları tüm bu sonuçların her ikisinde de otomatik olarak sonuç döndürebiliyor olmalıdır. Bu makalede, sadece ortak durum yaklaşımına konsantre oluyoruz. 

5.5 Ortak Durumların Alt Bileşenleri

PageRank’in hangi ortak durum senaryolarını temsil etmeye yardım edebileceğini değerlendirmek açıklayıcı olacaktır. Wolverine Erişim referansında olduğu gibi, yüksek kullanımı olan sayfalar haricinde, PageRank ayrıca otoritenin veya güvenin ortaklığını da temsil edebilir. Örneğin, bir kullanıcı bir haberi, doğrudan New York Times ana sayfasından linklendiği için tercih edebilir. Tabi ki böylesi bir hikaye oldukça önemli bir sayfa tarafından paylaşıldığı için yüksek PageRank değerine sahip olacaktır. Bu durum ortak çalışmaya dayalı bir güven sağladığı için, bir sayfa eğer güvenilir veya otoriter bir kaynak tarafından bahsediliyorsa, onun da güvenilir veya otoriter olması olasıdır.  Benzer olarak, kalite veya önem bu tip bir döngüsel tanım içerisine uyuyormuş gibi görünmekte.

6. Kişisel PageRank

PageRank hesabının önemli bileşenlerinden birisi Web sayfaları ile ilgili olan E – vektörüdür. Bu vektör, dış köşesi olmayan döngülerdeki gibi değer batmaları (rank sink) için bir tür değer kaynağı olarak kullanılmaktadır (Bölüm 2.4). Bununla birlikte değer batmaları sorunlarını çözmekten ziyade, E’nin sayfa değerlerini ayarlamada güçlü bir parametre olduğu ortaya çıktı. Öngörüsel olarak E vektörü, rastgele bir gezginin düzenli olarak yöneldiği web sitelerinin dağılımına karşılık gelmektedir. Aşağıda gördüğümüz üzere, Web’e ilişkin geniş genel bakış açılarının verilmesi için kullanılabileceği gibi, kişisel veya belirli bir kişiye yönelik bakış açıları için de kullanılabilir.

Çoğu deneyimizi E vektörü tüm web sitesi sayfalarında ||E||1 = 0.15 değerine sahip ve eş dağılımlı olacak şekilde gerçekleştirdik. Bu değer, periyodik olarak rastgele web sayfalarına geçiş yapan rastgele bir gezgine karşılık geliyor. Bu E için oldukça demokratik bir seçim çünkü, tüm web sayfaları sadece var olmaları nedeniyle değerlere sahip oluyorlar. Her ne kadar bu teknik bir hayli başarılı olsa da, önemli bir sorunu da bulunmakta. Çok sayıda ilgili linki olan site aşırı yüksek değerler alabiliyor. Bunlara telif hakkı uyarıları, sorumluluk retleri ve büyük miktarda iç linkli mail listesi arşivleri örnek olarak gösterilebilir.

Diğer bir ekstrem koşul ise E’nin tümüyle tek bir web sayfasından oluşmasıdır. Böylesi iki E değerini Netscape ana sayfası için ve ünlü bilgisayar bilimci John McCarthy için test ettik. Netscape ana sayfası için, page rank’leri Netscape ana sayfasını varsayılan sayfası olarak ayarlamış amatör bir kullanıcının bakış açısından üretmeyi denedik. John McCarthy’nin ana sayfasında ise page rank’leri, bize kendi ana sayfasında yer alan linklere göre yeterli miktarda içeriksel bilgi veren bir kişiyi ele alarak hesaplamak istiyoruz.

Her iki durumda da, yukarıda bahsedilen mail listesi sorunu gerçekleşmeyecektir. Ve, her iki durumda da, şahsi ana sayfalar en yüksek PageRank değerlerine sahip olacak ve devam eden linkler bu değeri takip edecektir.

 

Tablo 2: Farklı İki Görüntü İçin Page Rank’ler: Netscape’ karşılık John McCarthy

Bu noktadan sonra uyumsuzluk azalmaktadır. Tablo 2’de farklı sayfa çeşitleri için, sonuç sayfası page rank oranlarını gösteriyoruz. Bilgisayar bilimi ile ilgili sayfalar, Netscape değerinden daha yüksek McCarthy-değerine sahip ve Stanford’daki bilgisayar bilimi ile ilgili sayfalar önemli miktarda McCarthy-değerine sahip. Örnek olarak, başka bir Stanford Bilgisayar Bilimi Departmanı üyesi McCarthy-değerinde yüzde altıdan daha yüksek bir değere sahiptir. Page rank’lerin oranlar olarak görüntülendiğini not edelim. Bunun  sıralamanın en üstünde PageRank’de büyük farklılıkları sıkıştırma gibi bir etkisi var.

Böylesi kişiselleştirilmiş page rank’lerin bunlara kişisel arama motorları da dahil olmak üzere birkaç uygulaması olabilir. Bu arama motorları, ilgi duydukları konularda, kişilerin ana sayfalarını veya yer işaretlerini(bookmark) kullanarak önemli tahminlerde bulunabilir ve kullanıcıları büyük miktarda sorundan kurtarabilir. Buna örnek olarak Appendix A’da “Mitchell” sorgusu ile ilgili bir örnek gösterdik. Bu örnekte, her ne kadar internette Mitchell adında pek çok kişi bulunsa da, bir numaralı sonuç John McCarthy’nin meslektaşı olan John Mitchelle’e ait. 

6.1 Ticari Çıkarın Manipülasyonu

Bu türde kişiselleştirilmiş PageRank’ler ticari çıkarın manipülasyonuna karşın bağışıklıdır. Bir sayfanın yüksek PageRank değeri alması için, ikna etmesi veya önemsiz çok sayıda sayfadan link alması gerekir. En kötüsü, önemli sitelerde reklam satın alma forumda(linkler) manipülasyona sahip olabilirsiniz. Fakat, bu durum maddi bir karşılığı olması nedeniyle kontrol altında gibi görünüyor. Manipülasyona karşın bağışık olmak aşırı derecede önemli bir özellik. Bu tür reklam amaçlı manipülasyonlar arama motorlarına ciddi bir sorun oluşturuyorlar ve oldukça faydalı olabilecek özelliklerin uygulanmasını zor hale getiriyorlar. Örneğin dökümanların hızlı şekilde güncellenmesi oldukça aranan bir özellik, fakat bu özellik arama motorları sonuçlarını manipüle etmek isteyen kişiler tarafından suiistimal ediliyor.

Eşit dağılım gösteren E ve tek sayfa E’sinin iki ekstrem durumu arasındaki uzlaşma, E’nin tüm web serverlarındaki tüm kök sayfa seviyelerinin içeriyor. Bunun PageRank’lerde bir miktar manipülasyona izin vereceğini fark edebilirsiniz. Bu sistemi manipüle etmek isteyen birisi oldukça basit bir şekilde tümü belirli bir sayfaya yönlenen çok fazla sayıda kök seviye server oluşturabilir.  

7. Uygulamalar 

7.1 Web Trafiğinin Hesaplanması

PageRank kabaca rastgele bir gezgine karşılık gediği için (Bölüm 2.5), PageRank’in gerçek kullanıma nasıl karşılık geldiğini görmek ilginç olacaktır. Web sayfalarının NLANR [NLA] proxy önbelleğinden erişim sayılarını kullandık ve bunları PageRank ile karşılaştırdık. NLANR verisi birkaç aylık bir süreyi içeren, birkaç ulusal proxy önbelleğinden geliyordu ve en yüksek hit sayısı 638,657 ile Altavista olmak üzere 11,817,665 tekil URL’den oluşmaktaydı. Bizim 75 milyon URL veri tabanımızla önbellek verisinin kesişimin de 2.6 milyon sayfa yer almaktaydı. Bu veri setlerinin analitik olarak karşılaştırılmaları, çeşitli nedenlerden dolayı aşırı derecede zordur. Önbellek erişim verisindeki URL’lerin çoğu, insanların ücretsiz email servislerindeki kişisel mesajları içerisinde yer alıyor. Yinelenen server isimleri ve sayfa isimleri ciddi bir sorun. Eksiklik ve eğilim hem PageRank verisi hem de kullanıcı verisi için bir sorun. Bununla birlikte, veride bazı ilginç trendler görüyoruz. Önbellek verisinde pornografik verilerin yüksek seviyede bir kullanımı görünmekte, fakat bu siteler genelde düşük PageRank değerlerine sahipler. Bunun nedeninin insanların kendi sitelerinden pornografik sitelere link vermek istememeleri olduğunu düşünüyoruz. Bu tekniği kullanıp, PageRank ve kullanım arasındaki farklara bakarak, insanların bakmaktan hoşlandıkları fakat web sitelerinde bahsetmek istemedikleri şeyleri bulmak mümkün olabilir. Bazı sitelerin çok yüksek kullanımı bulunurken, düşük PageRank değerleri olabiliyor, aynı Netscape.yahoo.com’da olduğu gibi. Bu noktada veri tabanlarımızdan çıkarılmış önemli bir backlink olduğuna inanıyoruz (web’in sadece belirli bir bölümünün link yapısına sahibiz). Kullanım verisini PageRank için bir başlangıç vektörü olarak kullanmak ve daha sonra PageRank’i birkaç kez itere etmek mümkün olabilir. Bu kullanım verisindeki boşlukları doldurmaya da fırsat verebilir. Her durumda, bu tür karşılaştırmalar gelecek çalışmalar için ilginç bir konu haline geliyor. 

7.2 Backlink Tahminleri için PageRank

PageRank’i doğrulayan durumlardan birisi backlink tahminidir. [CGMP98]’de webi nasıl daha etkili crawl edebileceğimizi, öncelikle dökümanları crawl ederek tartışıyoruz. Stanford testlerinde PageRank’in, gelecek atıfların tahmin edilmesinde, atıf sayısının kendisine göre daha iyi bir tahmin sunduğunu gördük.

Deney sistemin tekbir URL ile başladığını ve başka bir bilgiye ihtiyaç duymadığını varsayıyor ve hedef mümkün olduğu kadar optimum düzene yakın şekilde sayfaların crawl edilmesini denemeyi içeriyor. Optimal düzen, sayfaların, tamamıyla bir değerlendirme fonksiyonuna göre değer sırasıyla crawl edilmesidir. Buradaki amaç gereği, değerlendirme fonksiyonu basit olarak, tüm bilgiyi sağlayan atıf sayısıdır. Buradaki kazanç, değerlendirme fonksiyonunu için gerekli olan tüm bilginin, tüm dokümanlar crawl edilene kadar kullanılabilir olmamasıdır. Görünen o ki, eksik verinin kullanımında, PageRank crawl işlemini belirli bir sıraya koymada, bilinen atıfların sayısına göre çok daha efektif bir yöntemdir. Diğer bir deyişle, PageRank ölçülecek şey atıf sayısı olsa dahi, PageRank atıf sayımına göre daha iyi bir tahmin sunmaktadır! Bunun açıklaması PageRank’in, atıf sayımının takılı kaldığı yerel maksimumu es geçebilmesidir. Örneğin, atıf sayımı Stanford CS web sayfaları gibi yerel birikimlerde, genişlediği ve diğer alanlarda yüksek atıflı sayfaları da bulduğu için takılma eğilimindedir. PageRank çabucak Stanford ana sayfasının önemli olduğunu bulur ve geniş, efektif aramalarda sonuçlarda tercihlendirme yapar.

PageRank’in atıfları tahmin etmedeki bu yeteneği PageRank kullanımının doğru tercih olmasındaki güçlü bir belirteçtir. Her ne kadar web’in atıf haritasını tümüyle çıkarmak oldukça zor olsa da, PageRank atıf sayısı yaklaşımı açısından, atıf sayımlarının kendisinden daha iyidir.

Şekil 7: PageRank Proxy 

7.3 Kullanıcı Hareketleri: PageRank Proxy

Kullanıcıların her bir linki, PageRank’i ile birlikte gördüğü bir web proxy uygulaması geliştirdik. Bu oldukça kullanışlı, çünkü kullanıcılar ona tıklamadan önce link hakkında bilgiye sahip oluyorlar. Şekil 7 proxy’nin bir görüntüsünü veriyor. Kırmızı çubukların uzunluğu URL’nin PageRank kaydıdır. Büyük kuruluşlar olan, Stanford Üniversitesi gibi kuruluşların devamında araştırma grubunun ve sonrasında kişilerin gösterildiği yüksek değerlere (rank) sahip olduğunu görüyoruz. Ayrıca ACM’nin de oldukça yüksek PageRank değerine sahip olduğunu, fakat Stanford Üniversitesi kadar olmadığını görüyorsunuz. İlginç bir şekilde, sayfaların bu altında notlar olan PageRank görünümleri, bir profesör için yanlış URL’yi profesörün utanç duyulacak kadar düşük PageRank’i olması nedeniyle parlak şekilde görünür hale getiriyor. Sonuç olarak bu araç sayfaların yazarlığı için olduğu kadar hareket için de kullanışlı görünüyor. Bu proxy diğer arama motorlarından sonuçlara bakmak ve Yahoo listeleri gibi içerisinde çok sayıda link bulunduran sayfalara bakmak için oldukça kullanışlı. Bu proxy, insanlara uzun bir listede hangi linklerin ilginç gelebileceğinin belirlenmesinde yardımcı oluyor. Veya, eğer kullanıcı baktığı linkin “önemlilik” spekturumunda hangi değere sahip olduğuna ilişkin bir fikir sahibiyse, proxy’yi kullanarak çok daha hızlı bir şekilde tarama yapabiliyor olması gerekir. 

7.4 PageRank’in Diğer Kullanımları

PageRank’in ana hedefi backlinklerin bir sıralanma yolunun bulunmasıydı. Bu nedenle eğer bir doküman için çok sayıda backlink mevcutsa, “en iyi” backlinkler ilk önce gösterilecekti. Böylesi bir sistem geliştirdik. PageRank’e göre sıralanan backlink görüşü aynı zamanda rekabeti anlamak açısından da oldukça ilginç olabiliyor. Örneğin, bir haber sitesi yöneten bir kişiler, rakiplerinin önemli bir backlink alıp almadığını düzenli olarak takip etmek isterler. Ayrıca, PageRank kişilerin bir sitenin güvenilir olup olmadığını anlamasında yardımcı olabilir. Örneğin, bir kullanıcı doğrudan Stanford anasayfası tarafından atıf verilmiş bir bilgiye güven duyma eğilimindedir.

8. Sonuç

Bu makalede, World Wide Web içerisindeki tüm sayfaları tek bir numaraya göre, onların PageRank’ine göre yoğunlaştırmak gibi zorlu bir görevi gerçekleştiriyoruz. PageRank tüm dünyadaki tüm web sayfalarının, içeriklerinden bağımsız olarak sadece Web’deki grafik yapısındaki konumları baz alınarak oluşturulan bir değerdir.

PageRank’i kullanarak, arama sonuçlarını daha önemli ve daha merkezi Web sayfalarına öncelik vererek sıralamayı başardık. Deneylerde bunun kullanıcılara daha yüksek kalitede arama sonuçları sağladığı görülüyor. PageRank’in arkasındaki mantık, Web sayfalarına harici bilgileri kullanmasıdır – backlinklerini, yani bir nevi meslektaş yorumlarını kullanmaktadır. Ek olarak, “önemli” sayfalardan gelen backlinkler ortalama sayfalardan gelen backlinklerden daha önemlidirler. Bu PageRank’in tekrarlamalı tanımını da içine almaktadır (Bölüm 2.4).

PageRank yaygın kullanımı olan ve çoğu sorguya cevap olabilecek küçük bir doküman setinin filtrelenmesi için kullanılabilir. Tüm veri tabanına, küçük bir veri tabanı bir sorguya cevap verebilmek için yeterli olmadığında ihtiyaç duyulur. Sonuç olarak, PageRank bir kümenin merkezinin görüntülenmesi için temsilci sayfaların bulunmasına yardımcı olmak için iyi bir yol olabilir.

PageRank için aramaya ek olarak trafik hesaplamalarının ve kullanıcı hareketlerinin de dahil olduğu birkaç uygulama bulduk. Ayrıca, belirli bir perspektiften Web’in bir görünümünü oluşturan kişiselleşmiş PageRank’leri de üretebiliriz.

Toplamda, PageRank ile ilgili deneylerimiz, Web grafiği yapısının, çeşitli bilgi getirme görevleri açısından kullanışlı olduğunu öneriyor.

Referanslar

[BP] Sergey Brin and Larry Page. Google search engine. http://google.stanford.edu.

[CGMP98] Junghoo Cho, Hector Garcia-Molina, and Lawrence Page. Ecient crawling through url ordering. In To Appear: Proceedings of the Seventh International Web Conference (WWW 98), 1998.

[Gar95] Eugene Gareld. New international professional society signals the maturing of scientometrics and informetrics. The Scientist, 9(16), Aug 1995. http://www.the-scientist. library.upenn.edu/yr1995/august/issi_950821.ht%ml.

[Gof71] William Go man. A mathematical method for analyzing the growth of a scienti c discipline. Journal of the ACM, 18(2):173{185, April 1971.

[Kle98] Jon Kleinberg. Authoritative sources in a hyperlinked environment. In Proceedings of the Nineth Annual ACM-SIAM Symposium on Discrete Algorithms., 1998.

[Mar97] Massimo Marchiori. The quest for correct information on the web: Hyper search engines. In Proceedings of the Sixth International WWW Conference, Santa Claram USA, April, 1997, 1997. http://www6.nttlabs.com/HyperNews/get/PAPER222.html.

[MF95] Sougata Mukherjea and James D. Foley. Showing the context of nodes in the worldwide web. In Proceedings of ACM CHI'95 Conference on Human Factors in Computing Systems, volume 2 of Short Papers: Web Browsing, pages 326{327, 1995.

[MFH95] Sougata Mukherjea, James D. Foley, and Scott Hudson. Visualizing complex hypermedia networks through multiple hierarchical views. In Proceedings of ACM CHI'95 Conference on Human Factors in Computing Systems, volume 1 of Papers: Creating Visualizations, pages 331{337, 1995. [MR95] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

[NLA] NLANR. A distributed testbed for national information provisioning. http://ircache. nlanr.net/Cache/. [PB98] Lawrence Page and Sergey Brin. The anatomy of a large-scale hypertextual web search engine. In To Appear: Proceedings of the Seventh International Web Conference (WWW 98), 1998.

[Pit97] James E. Pitkow. Characterizing World Wide Web Ecologies. PhD thesis, Georgia Institue of Technology, June 1997.

[PPR96] Peter Pirolli, James Pitkow, and Ramana Rao. Silk from a sow's ear: Extracting usable structure from the web. In Michael J. Tauber, Victoria Bellotti, Robin Je ries, Jock D. Mackinlay, and Jakob Nielsen, editors, Proceedings of the Conference on Human Factors in Computing Systems : Common Ground, pages 118{125, New York, 13{18 April 1996. ACM Press.

[San95] Neera ja Sankaran. Speculation in the biomedical community abounds over likely candidates for nobel. The Scientist, 9(19), Oct 1995. http://www.the-scientist.library. upenn.edu/yr1995/oct/nobel_951002.html%.

[Spe97] Ellen Spertus. Parasite: Mining structural information on the web. In Proceedings of the Sixth International WWW Conference, Santa Claram USA, April, 1997, 1997. http://www6.nttlabs.com/HyperNews/get/PAPER206.html.

[Til] Hope N. Tillman. Evaluating quality on the net. http://www.tiac.net/users/hope/ findqual.html.

[WVS+ 96] Ron Weiss, Bienvenido Velez, Mark A. Sheldon, Chanathip Manprempre, Peter Szilagyi, Andrzej Duda, and David K. Gi ord. HyPursuit: A hierarchical network search engine that exploits content-link hypertext clustering. In Proceedings of the 7th ACM Conference on Hypertext, pages 180{193, New York, 16{20 March 1996. ACM Press.

Ek Bölüm A

Bu ek bölüm Google kullanılarak elde edilen çeşitli sorgu sonuçlarını kapsıyor. Bunlardan ilki “Digital Libraries” için eş dağılımlı E kullanılarak. Diğeri ise sadece John McCarthy’nin ana sayfasını içeren E’yi kullanan “Mitchell” sorgusudur.