PageRank Algoritması

Orijinal PageRank algoritması, Lawrence Page ve Sergey Brin tarafından şu şekilde formüle edilmiştir:

PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))

• PR(A), A sitesinin pagerank’ını
• PR(T1), A sayfasına linklenen T1 sayfalarının pagerank’ını
• C(T1), T1 sayfasındaki giden linklerin sayısını
• D ise 0-1 arasında kaydedilen sönüm katsayısını ifade eder.

Yani, öncelikle, PageRank’ın web sitelerini bir bütün olarak sıralamaz ama her sayfa teker teker belirlenir. Dahası, A sayfasının PageRank’ı, A sayfasına linklenen sayfaların PageRank’ları tarafından tekrar tekrar tanımlanır.

A sayfasına linklenen T1 sayfalarının PageRank’ı, A sayfasının PageRank’ını aynı oranda etkilemez. PageRank algoritmasının içinde, bir T sayfasının PageRank’ı, T sayfasındaki C(T) giden linklerin sayısı tarafından her zaman etkilenir. Bu demektir ki, bir T sayfası ne kadar çok giden linke sahip olursa, A sayfası, T sayfası üzerindeki linkten bir o kadar az faydalanır.

T1 sayfalarının ağırlıklı PageRank’ı bundan sonra anlamlandırılır. Bunun sonucunda, her zaman A sayfalarının PageRank’ını artıracak bir A sayfası için ek gelen linkler oluşur.

Son olarak, T1 sayfalarının hepsinin ağırlıklı PageRank’ının toplamı, 0-1 arası kaydedilebilen bir sönüm katsayısı d ile çarpılır. Böylece, PageRank’ın uzantısı, azaltıldığı diğer bir sayfa linklemesi tarafından bir sayfa için yararlı olur.

RASTGELE İNTERNET GEZGİNİ MODELİ

Yazarlar, PageRank’ı internette surf yapanlar içeriğe bakmadan gelişigüzel linklere tıkladığı bir kullanıcı modeli olarak düşünürler.

Gelişigüzel surf yapanlar, sayfanın PageRank’ından türeyen kesin bir olasılıkla birlikte bir web sayfasını ziyaret ederler. Bir link üzerine tıklayan gelişigüzel surf yapanların olasılığı, sadece o sayfadaki linklerin sayısı tarafından verilir. Bu sebeple, bir sayfanın PageRank’ı, linklendiği bir sayfaya tamamen geçiş yapmaz ama sayfadaki linklerin sayısı tarafından bölünür.

Böylece, bir sayfaya ulaşan gelişigüzel surf yapanlar için olasılık, bu sayfaya verilen linkleri izleyen gelişigüzel surf yapanlar için olasılıklarının toplamıdır. Şimdi, sönüm katsayısı d tarafından bu olasılık azaltılır. Rastgele İnternet Gezgini Modeli içindeki doğrulama, böylece, sonsuz bir link sayısına tıklamayan ama bazen sıkılıp rastgele başka sayfaya atlayan surf yapanlar olur.

Linklere tıklamayı bırakmayan gelişigüzel surf yapanlar için olasılık, 0-1 arası kaydedilebilen olasılık derecesine bağlı olan sönüm katsayısı d tarafından verilir. Daha yüksek d, gelişigüzel surf yapanların linklere tıklamaya devam edeceği ihtimalini de yükseltir. Surf yapanlar linklere tıklamayı bıraktıktan sonra rastgele başka sayfaya atlarken, olasılık bu yüzden algoritma içine bir sabit (1-d) olarak uygulanır. Gelen linklere bakılmaksızın, gelişigüzel surf yapanların başka sitelere atlama olasılığı her zaman vardır, bu yüzden bir sayfa her zaman minimum PageRank’a sahip olur.

PAGERANK ALGORİTMASININ FARKLI BİR GÖSTERİMİ

PageRank algoritmasının ikinci versiyonu şöyledir. Algoritmanın bu ikinci sürümünde, bir A sayfasının PageRank’ı aşağıdaki gibidir:

PR(A) = (1-d) / N + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))

Burada N, web’deki bütün sayfaların toplam sayısıdır. Algoritmanın bu ikinci versiyonu aslında birincisinden çok da farklı değildir. Rastgele İnternet Gezgini Modeli’ne ilişkin, bir sayfanın ikinci PageRank versiyonu, birçok linke tıkladıktan sonra o sayfaya ulaşan surf yapan bir kişi için olan esas olasılığıdır. Daha sonra PageRank’lar web sayfaları üzerinde bir olasılık dağılımı oluşturur, yani bütün sayfaların PageRank’larının toplamı bir tane olur.

Aksine, birinci versiyon algoritmada bir sayfaya ulaşan gelişigüzel surf yapan kişi için olasılık, web sayfalarının toplam sayısı tarafından etkilenmektedir. Böylece, bu versiyonda PageRank, bir sayfayı ziyaret eden gelişigüzel surf yapan kişi için beklenen bir değerdir. Eğer webin 100 sayfası varsa ve bir sayfanın 2 değerinde PageRank’ı varsa, bir gelişi güzel surf yapan birey eğer 100 kez restart yaparsa, o sayfaya ortalama olarak iki katı kadar ulaşır.

Yukarıda belirtildiği gibi, iki algoritma versiyonu da temelde birbirilerinden farklı değildir. İkinci versiyon PageRank, birinci versiyon kullanılarak hesaplanabilen PAgeRank’ı uygun olarak edinmek için web sayfalarının toplam sayısı tarafından çarpılmalıdır.

Aşağıdaki örnekte, birinci versiyon algoritma kullanılacaktır. Çünkü hesaplaması daha kolay yapılabilir.

PAGERANK ÖZELLİKLERİ

PageRank özellikleri kısa bir örnekle gösterilebilir.

A, B, C sayfalarından oluşan küçük bir web sitesi vardır. A sayfası B ve C sayfasına, B sayfası C sayfasına ve C sayfası da A sayfasına linklenmiştir. sönüm katsayısı d genelde 0.85 olarak alınır ancak hesaplama daha kolay olsun diye bu örnekte 0.5’e ayarlanmıştır. sönüm katsayısı d’nin kesin değerinin gerçekte PageRank üzerinde etkileri vardır ama PageRank’ın temel ilkelerine etki etmez. Böylece PageRank hesaplaması için aşağıdaki eşitlikleri elde ettik:

PR(A) = 0.5 + 0.5 PR(C)
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))

Bu eşitlikler kolayca çözülebilir. Her sayfa için aşağıdaki PageRank değerlerini elde ettik:

PR(A) = 14/13 = 1.07692308
PR(B) = 10/13 = 0.76923077
PR(C) = 15/13 = 1.15384615

Bütün sayfaların PageRank’ları toplamının 3 olduğu açıktır ve böylece web sayfalarının toplam sayısına eşit olur. Yukarıda gösterildiği gibi, bu, basit örneğimiz için spesifik bir sonuç değildir.

PAGERANK’IN YİNELEMELİ HESAPLAMASI

Gerçek webin boyutundan dolayı, Google arama motoru, PageRank değerlerinin tahmini, yinelemeli hesaplamasını kullanır. Bu demektir ki, her bir sayfa ilk başlayan değeri tahsis eder ve bütün sayfaların PageRank’ları, PageRank algoritması tarafından belirtilen eşitliklere dayalı hesaplama çemberlerinde hesaplanır. Yinelemeli hesaplama yine yukarıdaki örnekteki 3 sayfalı web sayfası üzerinden gösterilebilir. Her bir sayfanın başlayan PageRank değeri 1 olarak tahsis edilmiştir.

Sadece birkaç yinelemeden sonra gerçek PageRank değerlerinin iyi bir tahmini elde ettik. Bütün web sayfasının PageRank değerlerinin iyi bir tahminine ulaşmak için yaklaşık 100 yinelemeye gerek vardır.