PageRank
Algoritma > Sönümleme Faktörü

Bağlantılar arasında rastgele dolaşan bir internet ziyaretçisinin, bir süre sonra gezinmeyi sonlandıracağını öngören PageRank teorisi, her adımda bağlantıları takip etme olasılığını d sönümleme faktörüyle tanımlar. Bu olasılık, rastgele bir sayfaya atlama olasılığı olan 1-d'ye eşittir. Çeşitli araştırmalarda farklı oranlar test edilmiş olsa da, sönümleme faktörü için 0,85 civarında bir değer genel kabul görmüştür.
Bu değer, 1'den çıkartılı ve daha sonra sönümleme faktörü (d) ile toplam PageRank puanının çarpımına eklenir. Adından da anlaşılacağı gibi sönümleme faktörü, elde edilen PageRank puanlarını aşağı çeker.
\displaystyle PR(A)=1-d+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right)
Bazı algoritma varyasyonlarında, sönümleme faktörünün (d) 1'den çıkarıldığında elde edilen değer, koleksiyondaki sayfa sayısına (N) bölünür.
\displaystyle PR(A)={1-d \over N}+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right)
Bu formül N ile taraf tarafa çarpıldığında iki formül arasındaki fark açığa çıkar: İlk formüldeki PageRank değerlerinin toplamının 1 olması, ikinci formülde ise toplamın N olmasıdır. Page ve Brin'in makalesindeki "tüm PageRank'lerin toplamı 1'dir" ifadesi " ve diğer Google çalışanlarının iddiaları yukarıdaki formülün ilk varyantını desteklemektedir.
Esasen, Page ve Brin, en popüler makaleleri olan "Büyük Ölçekli Hiper Metinsel Web Arama Motorunun Anatomisi"nde iki formülü karıştırken yanlışlıkla ikinci formülün web sayfaları üzerinde bir olasılık dağılımı oluşturduğunu öne sürmüşlerdi.
Teori, birkaç tıklamanın ardından arzu ettiği sayfaya ulaşan ve daha sonra rastgele bir sayfaya geçiş yapan rastgele bir internet ziyaretçisi modelini kullanmaktadır. Bir sayfanın PageRank değeri, rastgele gezinen bir kullanıcının bir bağlantıya tıklayarak o sayfaya gelme şansını yansıtır. Bu model, durumların sayfalar ve geçişlerin de sayfalar arasındaki bağlantılar olduğu bir Markov zinciri olarak yorumlandığında her durumun eşit derecede olası olduğu söylenebilir.
Örneğin, bir sayfanın başka sayfalara bağlantısı yoksa, bu sayfa bir "yutan durum" haline gelir ve rastgele gezinti sürecini sonlandırır. Rastgele gezgin bu durgun noktaya ulaşırsa, rastgele başka bir URL seçerek gezinmeye devam eder.
PageRank hesaplanırken, giden bağlantısı olmayan sayfaların koleksiyondaki tüm diğer sayfalara bağlantı verdiği varsayılır. Bu nedenle PageRank puanları diğer tüm sayfalar arasında eşit olarak bölünür. Başka bir deyişle, geçişlere sahip olan sayfalar için adil olmak gerekirse bu rastgele geçişler Web'deki tüm köşelere eklenir. Bu artık olasılık (d), ortalama bir sörfçünün tarayıcısının yer imi özelliğini kullanma sıklığına göre tahmin edilerek genellikle 0,85 olarak ayarlanır ve denklem aşağıdaki gibi gösterilir.
\displaystyle PR(p_{i})={\frac {1-d}{N}}+d\sum _{p_{j}\in M(p_{i})}{\frac {PR(p_{j})}{L(p_{j})}}
Burada  \displaystyle p_{1},p_{2},...,p_{N}incelenen sayfaları,  \displaystyle M(p_{i}),  \displaystyle p_{i}'ye bağlanan sayfalar kümesini,  \displaystyle L(p_{j}),  \displaystyle p_{j} sayfasındaki giden bağlantıların sayısı ve  \displaystyle N toplam sayfa sayısıdır.
PageRank değerleri, her sütunun toplamı bir olacak şekilde yeniden ölçeklendirilmiş, değiştirilmiş bitişiklik matrisinin baskın sağ özvektörünün girdileridir. İşte bu, Page ve Brin'in meşhur algoritmasının harika bir ölçüm olduğu noktadır:
\displaystyle \mathbf {R} ={\begin{bmatrix}PR(p_{1})\\PR(p_{2})\\\vdots \\PR(p_{N})\end{bmatrix}}
Burada özvektör  \displaystyle \mathbf {R}  denkleminin çözümüdür.
\displaystyle \mathbf {R} ={\begin{bmatrix}{(1-d)/N}\\{(1-d)/N}\\\vdots \\{(1-d)/N}\end{bmatrix}}+d{\begin{bmatrix}\ell (p_{1},p_{1})&\ell (p_{1},p_{2})&\cdots &\ell (p_{1},p_{N})\\\ell (p_{2},p_{1})&\ddots &&\vdots \\\vdots &&\ell (p_{i},p_{j})&\\\ell (p_{N},p_{1})&\cdots &&\ell (p_{N},p_{N})\end{bmatrix}}\mathbf {R}
Bitişiklik fonksiyonu  \displaystyle \ell (p_{i},p_{j}), j sayfasından i sayfasına giden bağlantıların sayısının, j sayfasındaki toplam giden bağlantı sayısına oranıdır.  \displaystyle p_{j} sayfası  \displaystyle p_{i}'ye bağlanmıyorsa bitişiklik işlevi 0'dır ve bu durum her j için standartlaştırılır:
\displaystyle \sum _{i=1}^{N}\ell (p_{i},p_{j})=1
Yani her bir sütunun öğelerinin toplamı 1'e eşit olduğu için PageRank matrisi, Markov zincirinin geçişlerini tanımlamak için kullanılan bir stokastik matristir ve ağ analizinde yaygın olarak kullanılan özvektör merkezilik ölçüsünün bir çeşididir.
Yukarıdaki değiştirilmiş bitişiklik matrisinin büyük özboşluğu nedeniyle, PageRank özvektörünün değerleri yalnızca birkaç yinelemede yüksek derecede doğrulukla tahmin edilebilir.
Google'ın kurucuları, orijinal makalelerinde, 322 milyon bağlantıdan oluşan bir ağ için PageRank algoritmasının 52 yinelemede kabul edilebilir bir sınıra yakınsadığını belirttiler. Bunun yarısı kadar bir ağda ise yakınsamanın yaklaşık 45 yineleme gerektirdiğini söyledir. Bu veriler sayesinde, algoritmanın çok iyi ölçeklenebileceği ve son derece büyük ağlar için ölçeklendirme faktörünün, n'nin ağın boyutu olduğu  \displaystyle \log n cinsinden kabaca doğrusal olacağı sonucuna vardılar.
Markov teorisinin bir sonucu olarak de bir sayfanın PageRank'inin, çok sayıda tıklama sonrasında o sayfaya ulaşma olasılığı olduğu söylenebilir. Bu durumda  \displaystyle t sayfadan kendisine geri dönmek için gereken tıklama (veya rastgele atlama) sayısının beklentisi iken bu olasılık  \displaystyle t^{-1}'e eşit olur.
Teori gereği, PageRank'in en ciddi dezavantajlarından biri eski sayfaları tercih etmesidir. Yeni bir sayfa, çok iyi bir sayfa bile olsa, Wikipedi gibi mevcut bir sitenin parçası olmadığı sürece çok fazla bağlantıya sahip olmayacaktır.
Bu dezavantaj yüzünden, arama sonuçları sıralamasını iyileştirmek ve reklam bağlantılarından para kazanmak için kötü niyetli SEO uzmanları PageRank'i manipüle etmeye yönelik uygulamalar yapmıştır. Bu uygulamalar, hangi sayfaların Web topluluğu tarafından gerçekten çok değerli olduğunu belirlemeyi amaçlayan PageRank kavramının güvenilirliğini ciddi şekilde etkilemiştir.
Ancak Google, Google Search Console üzerinden insanların ücretli ve spam bağlantıları bildirmelerini sağlayan mekanizması dahil olmak üzere, 2007'den bu yana yapay olarak PageRank değerini yükseltmek için yerleştirilen spam bağlantılar ve ücretli metin bağlantıları satan siteleri aktif olarak cezalandırıyor. Günümüzde ise ilk kez 2019 Webspam Raporu'nda adından "webspam" olarak bahsedilen SpamBrain başta olmak üzere, şirketin spam politikaları çerçevesinde tüm spam algılama sistemleri ile sadece bağlantılar değil internet üzerindeki tüm kötü niyetli uygulamalarla mücadele etmeye devam ediyor.