Pagerank ve Google

Pagerank için benden ısrarla link isteyen Aysun için yazıldı bu yazı, ona ithaf olunur…
Pagerankın ilk çıkış mantığı şu cümle ile özetlene bilir “insanların link verdigi site kötü site olamaz.insanlar bir siteye link veriyorsa, bu site iyi bir site olmalı…”
işte google bu sihirli cümleden yola çıkarak kuruldu, gelişti, gelişmeye devam etmektedir.Google’ un ilk yıllarında çogu kişi, pagerankın gücünün farkında degildi ve pek önemsemedi.Rakip arama motorları yahoo, msn ve altavista sanal dünyadaki milyarlarca sayfanın birbiri ile etkileşimine dayanan pagerank degerinin hesaplanmasının imkansıza yakın oldugunu ve sistem kaynaklarının boşuna bir ugraş içinde olacağı görüşünde birleşiyorlardı.Ancak yapılan deneyler sonucunda fark edildi ki gerçektende pagerank önemli bir etken idi.Bundan önceki yazımızda pagerank ve önemini okuya bilirsiniz.Bu yazımızda pagerankın matematiksel modellemesi üzerinde durulacaktır.
Pagerankın Google tarafından açıklanan formülü aşağıdadır:
PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))

formüldeki degişkenler şunlardır:

PR(A)= A sitesine ait pagerank degeri
d = “damped down” faktörü denilen özel bir katsayı ve 0.85 kabul edilmekte.
PR(Tn) = A sitesine link veren herhangi bir sitenin pagerank degeri.
C(Tn) = A sitene link veren herhangi bir sitedeki link sayısı.

Google yaptıgı açıklamalarda şunu belirtmiştir ki, sanal evrendeki tüm sitelerin ve sayfaların gerçek pagerank degerleri toplamı 1 sayısına eşit oldugu kabul edilmiştir.Bizde bu yaklaşımla yola çıkarak degişik linkleşme şemalarının pagerank degerine katkılarını inceleyecegiz.İlk örnegimizde linkleşmenin en basit hali olan karşılıklı link degişiminin etkilerini görelim.Yapacağımız tüm örneklerde her sitenin pagerank degeri ilk başta 1 kabul edilmiştir. Google denklemin gerçek köklerini bulabilmek için Newton Approximation method denilen iteleme yaklaşım methodunu kullanıyor. Özellikle Newton yaklaşım iterasyon methodu yüksek dereceden denklemlerin köklerini bulmak icin kullanılır, zira bu tarz yüksek dereceli denklemlerde b^2-4ac tarzı formülasyonlar çok başarılı olamamakta. Ancak Newton Yaklaşımı lineer değil geometrik olması ve bu sayede diğer benzeri iterasyon yöntemlerine göre aynı miktar yakınsamayı daha az sayıda basamak ile sagladığı için tercih ediliyor. Kabul edilebilir hata payına ulaşana kadar bulduğumuz denklem sonucunu yerine koyarak, sürekli yeni degerler çıkarmak, bulunan yeni degerleri yerine koyarak sonuca ulaşma sanatıdır iterasyon.

Pagerank örnek 1

Degerleri yerine koyarsak :
PR(A) yani A sitesine ait pagerank degeri 1 kabul edildi.
d= 0.85 katsayı degerinde oldugunu google bize söylüyor.
PR(B) yani B sitesine ait pagerank degeri 1 kabul edildi.
C(Tn) =1 A sitesinden ve B sitesinden dış dünyaya verilen link sayısı 1 oldugundan 1 alınırsa

Eger üsteki şekildeki iki siteninde ilk başta pagerank degerlerinin sıfır oldugunu kabul edip tekrar formulde yerine koyarsak:

Yeni iterasyonlar için yani buldugumuz degerleri tekrar tekrar formulde yerine koyarsak ve işleme devam edersek

3 kez işleme devam edersek

iterasyona devam edildikçe görülecektir ki, iki siteninde pagerank degeri 40.ncı iterasyondan sonra 1 degerine ulaşmakta.
kod | çalıştır

Eger yine iki site içinde ilk baştaki pagerank degerliklerini 40 kabul edersek yani PR(A)=40 ve PR(B) =40 kabul edilirse

Hesaplamaya devam edersek

İlk pagerank degerliklerini 40 kabul etsek bile yani 1 rakamından büyük bir sayı olsa bile iterasyon sonucu en basit linkleşme şeklinde bile belli iterasyon basamağı sonucu, Google un kabul ettiği 1 rakamına ulaşıyor.
Google her sitenin gerçek pagerank degerini yani iki linkin birbiri ile etkileşimini hesaplaya bilmek için 40 kez iterasyon yapmaktadır.
Pagerank örnek 2

programı çalıştır

Örnek 2 deki şekildeki bir linkleşme şeması sonucu yapılan 40 iterasyon sonucu her sitenin kazandıgı pagerank degeri aşağıdaki gibidir.
ilk başta tüm sitelerin pagerank degeri 0 kabul edildi.

Özet:En basit linkleşme şeklinin bile 40 iterasyon sonra 1 degerine ulaştığını varsayarsak:
D sitesi hiç bir siteden link almadıgından dolayı ilk başta 0 olan pagerank degerini 0.15 degerinde kalmıştır.
C sitesi 3 ayrı siteden link aldığından dolayı ve dışarıya sadece 1 link verdiginden dolayı pagerank degeri 1.58 olmuştur.
B sitesi 1 siteden link almış ve bir siteye link vermiş olmasına ragmen, mevcut pagerank degeri olan 1 sayısının bile altına inmiştir. Gelen linkin, giden linki hiç bir zaman eşitlemediğini bu örnek gösteriyor.

Pagerank örnek 3

programı çalıştır

Örnek 3 deki şekildeki bir linkleşme şeması sonucu yapılan 40 iterasyon sonucu her alt sayfanın ve dost sitenin kazandıgı pagerank degeri aşağıdaki gibidir.

Özet:
Eger başka sitelere link verirsek kendi alt sayfalarımıza gidecek pagerank degerini onlara vermiş olmaktayız. örnek 4′ü incelerseniz görürsünüz.

Pagerank örnek 4

programı çalıştır

Yine ilk başta tüm sayfalarımızın pagerank degeri sıfır kabul edilirse ve şekildeki gibi bir linkleşme yaparsak pagerank kazanımımız şekildeki gibi olur.

Pagerank örnek 5

Örnek 4 ün değişik bir şekli.Burada işte daha önceki pagerank yazımızda bahsettiğimiz olayı görmekteyiz karşılıksız link almanın önemi görülmektedir.A sitesi bizim sitemize karşılıksız olarak link vermekte ve sisteme pagerank girişi olmaktadır yani formulün pay kısmına yeni bir deger gelmiştir.Hem ana sayfamızın hemde alt sayfalarımızın pagerank degeri artmıştır.Örnek 4 de ana sayfamız 1.92 degerine sahip iken, sitemize aldığımız bir karşılıksız link sonucu ana sayfamızın pagerank degeri 3.31 degerine ulaştı.

Genel Özet
1- Çok fazla dost siteniz olursa, alt sayfalarınıza gidecek pagerank değeri, dost sitelerinize akar.Alt sayfalarınız güçsüz kalır.
2- Sitenizin pagerankının daha hızlı yükselmesi için, başka sitelerden karşılıksız link almanız gerekiyor.Link verdiginiz site, size link veriyorsa yani karşılıklı link degişim anlaşması yapmışsanız, pagerank getirisi çok az olduyor yada hiç olmuyor. Karşılıklı link degişiminin pek önemli olmadığını Örnek 1′i inceleyerekte görebilirsiniz.Karşılıklı link degişimi yapan iki sitenin ilk başta pagerank degerleri 1 kabul edilmişti, 40 iterasyon sonra yine pagerank degerleri 1 çıktı.
3- örnek5 i incelerseniz C sitesi, A sitesinden karşılıksız bir link aldığından dolayı (yani C sitesi, A sitesine link vermedi) ilk başta 1 kabul edilen pagerank degeri 40 iterasyon sonrasında 3kat artmıştır. C sitesinin aldığı bir karşıksız linkin önemi bir kez daha görülmüştür.
4- Eğer bencillik yapar kimseye link vermezseniz, web’in ağ olma özelliğini bozduğunuzdan dolayı google sitenizi cezalandırır.Pagerankınızın artmasını beklerken dahada düşer. Googlebot mutlaka sitenizden, başka sitelere kolaylıkla geçip gidebilmelidir.
5- Buradaki örnekler çok basit düzeyde olmasına ragmen her sayfanın birbiri ile link alışverişinin dogru hesaplanabilmesi için 40 iterasyon yapıldıgını görmektesiniz.Google milyarlarca sayfanın birbiri ile etkileşimini hesaplamak için yaptıgı matematiksel hesapları düşünürseniz, olayın boyutunu daha iyi kavrarsınız ve niye toolbar pagerankının güncellemesi 3 ayda bir güncelleniyor sorusunun cevabını kendinizde bulabilirsiniz. Çünkü trilyonlarca matematik işleminin dogru olarak hesaplanması yada dogruya yakın hesabı ancak bu kadar zaman alıyor…

Yazan: Mert ÖĞÜT
kaynak: www.gitme.net/pagerank.php
Kaynak göstererek bu yazıyı kullana bilirsiniz.Bu sayfaya link verebilirsiniz.
Burada yazılanlar, konu hakkında hiç bilgisi olmayanlara Pagerank ve link degişimimin önemi hakkında yüzeysel olarak bilgi vermek için yazılmıştır.

Kaynaklar:

• Michael Berry, Murray Browne, Understanding Search Engines: Mathematical Modeling and Text Retrieval. Second Edition, SIAM, Philadelphia. 2005.
• Sergey Brin, Lawrence Page, The antaomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, 33: 107-17, 1998. Also available online at http://infolab.stanford.edu/pub/papers/google.pdf
• Kurt Bryan, Tanya Leise, The $25,000,000,000 eigenvector. The linear algebra behind Google. SIAM Review, 48 (3), 569-81. 2006. Also avaiable at http://www.rose-hulman.edu/~bryan/google.html
• Google Corporate Information: Technology.
• Taher Haveliwala, Sepandar Kamvar, The second eigenvalue of the Google matrix.
• Amy Langville, Carl Meyer, Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 2006.
  This is an informative, accessible book, written in an engaging style. Besides providing the relevant mathematical background and details of PageRank and its implementation (as well as Kleinberg’s HITS algorithm), this book contains many interesting “Asides” that give trivia illuminating the context of search engine design.
• David Austin Grand Valley State University