Hakkında Künye

PageRank (Sayfa Değeri) Algoritması

Merhaba! Geçen ayki yazımda arama motoru iyileştirmesi ve dizinleme konusundan bahsetmiştim. Bu hafta ise, internet tarayıcılarının arşivledikleri sayfaları neye göre sıraladıklarının ölçüsü olan PageRank (sayfa değeri) kavramını ve nasıl hesaplandığını anlatmaya çalışacağım.

PageRank (Sayfa Değeri) nedir?

Önceki yazımda da belirttiğim gibi arama motorları internetteki sayfaların ne kadar ziyaretçi aldığını, içeriklerinin ne kadar kaliteli olduğunu ve bizim o sayfaya hangi olasılıkla ulaşabileceğimizi ölçmek için her sayfaya bir değer atar. Sayfa değeri veya sayfa popüleritesi diye Türkçeleştirilen PageRank, bu değere verilen addır. Sayfa değeri hesaplaması belli bir algoritmaya göre yapılmaktadır. Bu algoritma internet sayfalarının birbirleriyle olan ilişkilerini ölçebildiği gibi, aslında birbirleriyle bir şekilde ilişkili olan herhangi bir veri yığınına da uygulanabilir. Sayfa değeri bir sayfanın değerini hesaplarken, o sayfaya diğer sayfalardan verilen bağlantıları göz önüne alır. Ancak bağlantı veren sayfaların çok ziyaret edilmesi onların verdikleri bağlantıların değerini artırır; çünkü bu sayfalardan yola çıkarak diğer bir sayfaya ulaşma olasılığımız daha yüksektir.

Sayfa değeri birçok internet tarayıcısının sayfaları sıralandırmak için başvurduğu yöntemdir. Bu değer ile arama sonuçlarında sayfa ilk sıralarda yer alır. Örneğin; Google Araç Çubuğunu yüklediyseniz tarayıcınızın üst kısmında her sayfanın 0 -10 arasında değişen bir değere sahip olduğunu görebilirsiniz.

Sayfa Değeri Nasıl Hesaplanır?

Sayfa değeri’nin genel formülü:

Sayfa değeri kavramı ilk ortaya çıktığında bu şekildeydi. Gelişmiş internet tarayıcıları elbette bu formülün daha gelişmiş olanını kullanmaktadırlar.

Önce denklemdeki terimlerin ne anlama geldiğini tek tek açıklayalım.

  • t1…tn: Değerini bulmak istediğimiz sayfaya bağlantı veren sayfalar
  • PR(tn): Bize bağlantı veren sayfaların kendi değerleri
  • C(tn): Her sayfanın diğer sayfalara verdiği bağlantı sayısı
  • d: Tüm oranların toplamının 1’ i geçmesini engellemek için çarpılan katsayı (damping factor)
  • 1-d: (Tüm sayfaların sayısı) / (Sayfa değeri) oranının 1 olduğu varsayılarak d(PR(t1)/C(t1)…) değerine, d’den geri kalan değer burada eklenmiştir.

Bu denklemi basit bir örnekle açıklayalım:

Hiç bağlantı verilmeyen sayfaların sayfa değeri 0.15 olmaktadır; ama bazı söylentilere göre arama motorları hiç bağlantı almayan sayfaları dizinden silmektedir. Biz bağlantı veren sayfalardan ilerleyerek tahmin yapalım.

Başlangıç olarak internette A,B,C,D isimli 4 sayfamız olsun. Sayfa değeri’nin bu sayfalar arasında eşit olarak dağıldığını varsayarak her sayfaya 0.25 değerini verelim. Eğer bu sayfalardan B,C ve D sayfaları, A sayfasına bağlantı verirse her biri A sayfasına 0.25’lik bir katı sağlamış olur.  O zaman bütün Sayfa değeri A’da toplanmış olur çünkü tüm bağlantılar A’ya gitmektedir.

Toplam=0.75. O zaman başka bağlantıların da var olduğunu varsayarak devam edelim. B’nin C’ye , D’nin diğer tüm sayfalara bağlantı vermesi durumunda bağlantı değerleri dışa verilen bağlantılar arasında paylaşılır. Yani B A’ya 0.125 değerinde bir oy vermiş olur. D ise yalnızca 0.083. Yani ilk değerinin 1/3 ü kadar.

Diğer bir deyişle, dışarıdan verilen bağlantı değerlerinin toplamını, bu değerlerin normalleştirilmiş haline bölerek toplam sayfa değeri değerini bulabiliriz.

Katsayının Anlamı Nedir?

PageRank teorisindeki “d” değerini açıklamak için bir örnek verelim. İnternette gezinen ve sayfalara rastgele tıklayan ve en sonunda tıklamaktan vazgeçen birini düşünelim. Bu kişinin her adımda bir sonraki sayfaya da tıklama olasılığını veren “d”dir. Uzun hesaplamalar ve araştırmalar sonunda 0.85 değeri kabul edilmiştir. Azaltan katsayı (damping factor) 1 den çıkartılarak sayfa değeri değerine eklenir.

Bu formülün yaratıcıları olan Page & Brin formülün orjinalini yukarıdaki gibi açıklamaktadır. Ancak yayınladıkları kağıtta belirttikleri ifade bu formülün aşağıdaki gibi olduğunun işaretlerini vermektedir.

Yukarıdaki formülü açıklarken ufak bir yeri atladık. Şimdi o noktayı çözelim. İlk adımda, 4 sayfanın da başlangıç değerini 0.25 olarak almıştık. Peki, her sayfanın değerinin ona bağlantı veren sayfaların değeriyle hesaplandığını düşünürsek, henüz hiç sayfa değeri hesaplamamışken bir sayfanın diğer bir sayfaya verdiği değeri nasıl bulabiliriz? Bu soruna Google’ın yönteminden yola çıkarak yaklaşalım: “Sayfa değeri, tekrar tekrar uygulanan bir algoritma ile hesaplanır ve internetteki sayfaların normalleştirilmiş link matrisinin öz vektörüne (eigenvector) karşılık gelir.” Yani, Google, sayfaların son değerlerini bilmeden de hesaplamaya başlayabileceğimizi söylüyor. Bu garip gibi gözükse de aynı formülü hesaplanan geçici değerler üzerinden tekrar tekrar (iterative) uygulayınca, her seferinde olması gereken değere bir adım daha yaklaşıyoruz. Tek yapmamız gereken hesaplanan değerleri saklamak ve bir sonraki adımda o değerleri kullanarak yeni değerleri bulmaktır. Bu işlemi değerler artık belli bir sayıya yaklaşana ve adımlar arası değişme miktarları yeteri kadar azalana dek sürdürmemiz gerekir. Bunu bir örnek üzerinde görelim.

Birbirine bağlantı veren 2 sayfamız, A&B, olsun.

Her sayfa dışarıya tek bağlantı vermiştir. Yani C(A)=1 & C(B)= 1.

PR’nin sonunda kaç olacağını bilmiyoruz ama tahminimize 1’den başlayalım.

Sayı değişmedi. Tahminimiz doğru olabilir. Bu sefer tahminimize 0 ile devam edip görelim.

Birkaç adım daha gidelim.

Bu şekilde devam ettikçe sayıların arttığını görüyoruz. Peki,sayılar gitgide artıyor ve biz 1.0’de sürekli sabit bir değer vermeye bağladığını biliyoruz. Ya 1.0’i de geçerse?
Deneyelim ve görelim...

PR(A)=40,
PR(B)=40.

2.adım

Sayılar giderek azalıyor! Gördüğünüz gibi hangi sayıdan başlarsak başlayalım sonuç tek bir değere gidiyor ve “normalleştirilmiş olasılık dağılımı” (normalized probability distribution, yani her sayfanın ortalama Page Rank’i) 1.0’e yaklaşıyor.

Sonuç tek bir sayıya gitse de bunu kaç kere yapacağımızı nereden bilebiliriz? İnternette milyarlarca sayfa var ve arama motorları sayfaları tek tek geziyor.  Sayı bu kadar yüksek olunca adım sayısı da bağlantılı olarak milyonlara varıyor. Eğer “d” katsayımız çok yüksekse ya da çok düşükse, tek bir rakama ulaşmak yılları alabilir. Katsayıyı doğru seçmek adım sayımızı kısaltmamıza yardımcı olur.

Sayfa Değerinin Bulunması İçin Tek Bir Algoritma mı Kullanılıyor?

Elbette başka yöntemler de mevcuttur. Örneğin, HITS algoritması (Hyperlink-Induced Topic Search, bağlantı tabanlı konu arama), Jon Kleinberg tarafından geliştirilmiştir. Bu algoritma internet sayfalarını hem bağlantılara bakarak hem de sayfa içeriğine puan vererek sıralar. TrustRank analiz yöntemi ise Stanford Üniversitesi’nde Yahoo! araştırmacıları tarafından geliştirilmiştir. Bu yöntem yararlı ve yararsız (spam) sayfaları birbirinden ayırmak için kullanılır. Ancak sayfa değeri algoritması en yaygın kullanılan yöntem olduğu için diğer yöntemler çok popüler değildir.
Sonuç olarak, sayfa değeri yani PageRank iyi bir internet tasarımcısının iyi bilmesi ve sayfa tasarlarken göz önüne alması gereken bir kavramdır; çünkü sayfanın çok ziyaretçi alması buna bağlıdır. Bu yazıda sayfa değeri kavramını yeterince açık anlatabilmiş olduğumu umuyorum. İlerki sayılarda görüşmek dileğiyle…


Kaynaklar:

 



Işıl Özge Pekel
- 8 -