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 okuyabilirsiniz. Bu yazımızda pagerankın matematiksel modellemesi üzerinde durulacaktır.
Pagerankın Google tarafından açıklanan resmi formülü aşağıdadır:
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
formüldeki değişkenler şunlardır:
PR(A)= A sitesine ait pagerank degeri.Tüm siteler için ilk başta 1 kabul edilimektedir.
d = �damped down� faktörü denilen özel bir katsayı ve 0.85 kabul edilmekte.Pi sayısı gibi özel bir katsayı.
PR(Tn) = A sitesine link veren herhangi bir sitenin pagerank degeri.
C(Tn) = A sitesine link veren herhangi bir sitedeki link sayısı adeti.
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 hep. Bizde bu yaklaşımdan 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 (Sen bana link ver ben sana link vereyim mantığının incelemesi)
d | = 0.85 |
PR(A) | = (1 � d) + d(PR(B)/1) |
PR(B) | = (1 � d) + d(PR(A)/1) |
Degerleri yerine koyarsak :
PR(A) yani A sitesine ait ilk pagerank degeri 1 kabul ediliyor.
d= 0.85 katsayı degerinde oldugunu google bize söylüyor.
PR(B) yani B sitesine ait ilk pagerank degeri 1 kabul edildi.
C(Tn) =1 dir. Yani A sitesinden ve B sitesinden dış dünyaya verilen link sayısı adeti 1 oldugundan 1 alınırsa
PR(A) | = 0.15 + 0.85 * 1
= 1 |
PR(B) | = 0.15 + 0.85 * 1
= 1 |
| Sistemin ortalama pagerank değerlini Kontrol edelim | Pr(A)+ Pr(B)=2
2 /2 (Sistemde iki adet site mevcut oldugundan)= Sistemin ortalama pagerankı= 1 |
Eger üsteki şekildeki gibi linkleşen iki sitenin, ilk baştaki pagerank degerlerini bu seferde sıfır oldugunu kabul edip tekrar formulde yerine koyarlım,
yani illa ki ilk baştaki pagerank degerini 1 kabul etmem gerekmiyor.
Google bize diyor ki sistemin pagerank degerinin ortalaması 1 sayısına eşittir herzaman. Madem sistemin pagerank ortalaması 1 sayısına eşit olacak o halde bende, ilk kabul ettiğim pagerank degerini sıfır olarak seçip deneyerek denklemde yerine koymaya başlıyorum. Sonucunu bildigim formulün gerçek degerine ulaşabilmem için limit mantığı gereği iterasyon yapmam gerekiyor. Yani denklemin eğrisini tegetle kesiştire bilmem için kabul edilebilir hata payına yaklaşana kadar teget fonksiyonun egrisine yakınsayacak. (converge olacak) .
Birinci iterasyon sonucu |
|
| PR(A) | = 0.15 + 0.85 * 0
= 0.15 |
PR(B) | = 0.15 + 0.85 * 0.15
= 0.2775 |
Yeni iterasyonlar için yani buldugumuz degerleri tekrar tekrar formulde yerine koyarsak ve işleme devam edersek,
iterasyon demek buldugun sonucu tekrar denklemde yerine koy, yoluna devam et demek.
ikinci iterasyon sonucu |
|
| PR(A) | =0.15 + 0.85 * 0.2775
= 0.385875 |
PR(B) | = 0.15 + 0.85 * 0.385875
= 0.47799375 |
3 kez işleme devam edersek
üçüncü iterasyon sonucu |
|
| PR(A) | = 0.15 + 0.85 * 0.47799375
= 0.5562946875 |
PR(B) | = 0.15 + 0.85 * 0.5562946875
= 0.622850484375 |
iterasyona devam edildikçe görülecektir ki, iki siteninde pagerank degeri 40.ncı iterasyondan sonra 1 değerine yakınsamakta. Yani en basit pagerank linkleşme
şeması için en az 40 kez iterasyon yapıp, denkemin gerçek degerine ulaşabiliyoruz.
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
Birinci işlem sonucu |
|
| PR(A) | = 0.15 + 0.85 * 40
= 34.25 |
PR(B) | = 0.15 + 0.85 * 0.385875
= 29.1775 |
Hesaplamaya devam edersek
Birinci iterasyon sonucu |
|
| PR(A) | = 0.15 + 0.85 * 29.1775
= 24.950875 | pagerank deger 1 sayısına yaklaşıyor |
PR(B) | = 0.15 + 0.85 * 24.950875
= 21.35824375 | pagerank deger 1 sayısına yaklaşıyor |
İ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 yakınsıyor. Bir sitenin ilk başktaki pagerankını ister 1 kabul edelim ister 1000kabul edelim ama sonuçta sistemin ortalam pagerankı
herzaman 1 sayısına ulaşıyor. Google pagerank denklemi geregi 1 den büyük sayılar gittikçe küçülürken, birden küçük sayılarda 1 sayısına yakınsıyor.
Bu durumda şöyle düşünebiliriz: Google her sitenin gerçek pagerank degerini yani en basit iki linkin birbiri ile etkileşimini hesaplaya bilmek için en az 40 kez iterasyon yapmaktadır. İterasyon sayısının adetini belirleyen, denklemdeki site sayısı ve linkleşme şemasına göre çok çok karmaşıklaşabilmektedir. 10milyar web sitesinin biribiri
ile etkileşimi için trilyonlarca kez iterasyon yapılmakta ve hesaplanmakta. Sürekli yeni siteler açıldıgından dolayı sürekli denklemin pay ve paydası degişmekte ve iterasyon sayısı trilyonlarca kez degişmekte. Sistemin devasa büyüklüğünü sanırım tahmin edebilirsiniz artık. Birbirine paralel baglı onbinlerce bilgisayar bu matematik işlemini yapmakla görevli google binasında. Bu devasa boyuttaki iterasyonların hiç bir zaman hesaplanamayacağını düşünen microsoft hala pagerankı önemsemediginden
msn search bir arpa boyu yol alamadı :)
Arama sonuç kalitesinin artmasındaki en büyük etkenlerden biride, bu iterasyonların her geçen gün dahada sonuca yaklaşması olarakta düşünülebilir.
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 1 kabul edildi.
Özet:En basit linkleşme şeklinin bile google denklemi için en az 40 iterasyon sonra 1 degerine ulaştığını varsayarsak:
D sitesi hiç bir siteden link almadıgından dolayı ilk başta 1 olan pagerank degerini 0.15 degerine gerilemiştir. Link almadan başkasına link verirseniz elinizdeki pagerank degerinide kaybedersinizin açıkca göstergesidir.
C sitesi 3 ayrı siteden link aldığından dolayı ve dışarıya sadece 1 link verdiginden dolayı pagerank degeri 1.58 olmuştur. Link alarak pagerankınız artıyor.
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.
A sitesi yüksek pagerank degerlikli bir site olan C sitesinden link aldığından dolayı ilk başta 1 kabul edilen pagerank degerini 1,48 degerine çıkartmıştır.
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. Siteniz örümcek için çıkmaz sokak olmamalı hiç bir zaman.
5- Buradaki örnekler çok basit düzeyde olmasına ragmen her sayfanın birbiri ile link alışverişinin dogru hesaplanabilmesi için google denklemine göre en az 40 iterasyon yapıldıgını görmekteyiz. 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
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
