PageRank: Bağlantılardan sıralamaya giden matematik

İnternette milyarlarca sayfa var ve bir arama kutusuna yazdığınız iki kelime binlerce sayfada geçebilir. Hangisi önce gösterilmeli? 1990’ların sonunda bu soruya verilen en etkili cevaplardan biri, sayfaların içeriğine değil, aralarındaki bağlantılara bakan bir fikirdi: PageRank.

PageRank, Stanford Üniversitesi’nde doktora öğrencisi olan Sergey Brin ve Larry Page’in 1998’de yayımladığı çalışmada tanıtıldı ve Google arama motorunun ilk sürümünün temel parçalarından biri oldu. Ana fikir şudur: Bir sayfa, önemli sayfalardan bağlantı alıyorsa önemlidir. Bu yazıda bu döngüsel görünen tanımın nasıl hesaplanabilir bir sayıya dönüştüğünü dört sayfalık küçük bir örnekle göreceğiz. Bir uyarıyı da baştan yapalım: Bugünkü arama sıralaması tek bir formüle değil, çok sayıda etkene dayanır.

Sorun: Kelime saymak yetmez

Erken dönem arama motorları büyük ölçüde aranan kelimenin sayfada kaç kez ve nerede geçtiğine bakıyordu. Bu yaklaşımın iki zayıf noktası vardı. Birincisi, aynı kelimeyi içeren binlerce sayfa arasında hangisinin daha güvenilir olduğunu söyleyemiyordu. İkincisi, kelimeyi yüzlerce kez tekrarlayan bir sayfa sistemi kolayca yanıltabiliyordu.

Bağlantılar ise başka bir bilgi taşır. Bir sayfanın yazarı başka bir sayfaya bağlantı verdiğinde, bir bakıma “buraya bakmaya değer” demiş olur. Bilimsel makalelerde atıf sayısının bir ölçüt olarak kullanılması gibi, web’de de bağlantılar bir tür oy sayılabilir.

Ama her oy eşit değildir. Çok önemli bir sayfadan gelen tek bir bağlantı, kimsenin ziyaret etmediği yüz sayfadan gelen bağlantıdan daha anlamlı olabilir. Ayrıca yüz farklı sayfaya bağlantı veren bir sayfanın her bir bağlantısı, yalnızca bir sayfaya bağlantı veren bir sayfanınkinden daha az şey söyler.

Rastgele gezinen okur

PageRank bu iki sezgiyi bir olasılık modeliyle birleştirir. Web’de amaçsızca gezinen bir okur düşünelim:

• Okur bir sayfadayken, o sayfadaki bağlantılardan birini eşit olasılıkla seçip tıklar.
• Ama zaman zaman sıkılır ve bağlantıları bırakıp rastgele bir sayfaya atlar.

Bu okur çok uzun süre gezinirse, her sayfada geçirdiği zamanın oranı belirli bir değere yaklaşır. Bir sayfanın PageRank değeri bu orandır. Çok bağlantı alan sayfalara daha sık uğranır. Sık uğranan sayfalardan bağlantı alan sayfalara da daha sık varılır.

Okurun bağlantı tıklamaya devam etme olasılığına sönüm katsayısı denir ve d ile gösterilir. 1998’deki özgün çalışmada tipik değer olarak 0,85 kullanıldı. Yani okur her adımda %85 olasılıkla bir bağlantıyı izler, %15 olasılıkla rastgele bir sayfaya atlar.

N sayfalık bir ağda, bir X sayfasının değeri şöyle hesaplanır:

PR(X) = (1 − d) ÷ N + d × Σ [ PR(Y) ÷ L(Y) ]

Buradaki toplam, X’e bağlantı veren bütün Y sayfaları üzerinden alınır. L(Y), Y sayfasındaki bağlantı sayısıdır. Her sayfa değerini, bağlantı verdiği sayfalar arasında eşit paylaştırır. (Özgün makaledeki yazım biraz farklıdır; burada değerlerin toplamı 1 olacak biçimde yaygın kullanılan hâlini yazdık.)

Dört sayfalık örnek

Aşağıdaki küçük ağı biz kurduk. A, B, C ve D adlı dört sayfa var ve bağlantılar şöyle:

• A → B ve A → C (A’da iki bağlantı var)
• B → C
• C → A
• D → C

D’ye hiçbir sayfa bağlantı vermiyor. C ise üç sayfadan bağlantı alıyor. Sezgimiz C’nin en önemli sayfa olacağını söylüyor. Peki A’nın durumu ne?

N = 4 ve d = 0,85 alalım. O zaman (1 − d) ÷ N = 0,15 ÷ 4 = 0,0375 olur. Başlangıçta her sayfaya eşit değer verelim: 0,25.

Birinci adım:

• PR(A) = 0,0375 + 0,85 × (0,25 ÷ 1) = 0,25. A yalnızca C’den bağlantı alır, C’nin tek bağlantısı da A’ya gider.
• PR(B) = 0,0375 + 0,85 × (0,25 ÷ 2) ≈ 0,1438. B, A’nın iki bağlantısından birini alır.
• PR(C) = 0,0375 + 0,85 × (0,25 ÷ 2 + 0,25 + 0,25) ≈ 0,5688. C; A, B ve D’den bağlantı alır.
• PR(D) = 0,0375. D’ye gelen bağlantı olmadığı için yalnızca rastgele atlama payını alır.

Toplam yine 1’dir. Aynı hesabı yeni değerlerle tekrarlayalım. İkinci adımda A ≈ 0,521, B ≈ 0,144, C ≈ 0,298 olur. Üçüncü adımda A ≈ 0,291, B ≈ 0,259, C ≈ 0,413 çıkar. Değerler bir süre salınır ama giderek sakinleşir. Birkaç düzine adımdan sonra şu değerlere yerleşir:

Sayfa	Gelen bağlantı	PageRank (yaklaşık)
C	A, B, D	0,394
A	C	0,373
B	A	0,196
D	yok	0,038

Sonuç öğreticidir. C beklendiği gibi birinci. Ama yalnızca tek bir bağlantı alan A neredeyse C kadar yüksek. Çünkü A’ya bağlantı veren tek sayfa en önemli sayfa olan C’dir ve C bütün değerini yalnızca A’ya aktarır. Bağlantı sayısı kadar, bağlantının nereden geldiği de önemlidir.

Arkadaki matematik: Markov zinciri ve kararlı dağılım

Rastgele gezinen okur, matematikte Markov zinciri denen yapının bir örneğidir. Bir sonraki adımda nereye gidileceği yalnızca şu an bulunulan sayfaya bağlıdır. Sayfalar arası geçiş olasılıkları bir tabloya, yani bir matrise yazılabilir.

PageRank değerleri, bu matrisle çarpıldığında değişmeyen olasılık dağılımıdır. Doğrusal cebirde buna matrisin özvektörü denir. Yukarıda yaptığımız tekrar tekrar çarpma işlemine kuvvet yöntemi adı verilir. Rastgele atlama payı burada önemli bir iş görür. Hiçbir sayfanın sonsuza kadar kapalı bir döngüde sıkışıp kalmamasını ve hesabın tek bir cevaba yakınsamasını garanti eder.

Gerçek web’de hiç bağlantısı olmayan sayfalar da vardır. Okur böyle bir sayfaya geldiğinde nereye gideceğini bilemez. Yaygın çözüm, bu sayfalardan bütün sayfalara eşit olasılıkla geçildiğini varsaymaktır.

Bugünkü arama tek bir formül değil

PageRank’i “arama motorunun sırrı” gibi anlatmak yanıltıcı olur. Bugünkü sıralama sistemleri, sayfaların içeriği, aramanın amacıyla uyumu, güncellik, kullanılabilirlik ve güvenilirlik gibi çok sayıda etkeni birlikte değerlendirir. Bağlantıların analizi bu etkenlerden yalnızca biridir ve PageRank’in kendisi de 1998’den bu yana çok değişmiştir. Bir sistemin iç ayrıntıları kamuya açık olmadığından, bugün sıralamanın tam olarak nasıl yapıldığını bu yazıdaki formülden çıkarmak mümkün değildir.

PageRank’in asıl kalıcı etkisi başka bir yerde görülür. Bir ağdaki düğümlerin önemini ağın yapısından hesaplama fikri, web dışında da kullanılır. Bilimsel makalelerin atıf ağlarında, ulaşım ağlarında ve biyolojideki etkileşim ağlarında benzer yöntemler uygulanır.

Neden önemli?

PageRank, okulda ayrı ayrı öğrenilen fikirleri tek bir soruda buluşturur:

• Graflar: Sayfalar düğüm, bağlantılar yönlü kenardır. Grafların doğuşunu Euler ve Königsberg köprüleri yazımızda okuyabilirsiniz.
• Olasılık: Rastgele gezinen okur, her adımda olasılık kurallarına göre hareket eder. Olasılık hesabının kökenleri için Pascal ve Fermat yazımıza göz atabilirsiniz.
• Diziler ve yakınsama: Adım adım hesaplanan değerler bir limite yaklaşır.
• Oran: Her sayfa değerini bağlantıları arasında eşit paylaştırır.

Olasılık, diziler ve oran-orantı TYT ve AYT matematik konuları arasında yer alır. Ayrıntılı listeyi ne öğrettiğimizi anlattığımız sayfada bulabilirsiniz.

Kapanış

PageRank’in güzelliği, “önemli sayfa, önemli sayfaların işaret ettiği sayfadır” gibi kendi kendine dönen bir tanımı hesaplanabilir hâle getirmesindedir. Rastgele gezinen hayalî bir okur, birkaç satırlık bir formül ve sabırla tekrarlanan bir hesap, dört sayfalık bir ağdan milyarlarca sayfalık bir ağa kadar aynı mantıkla çalışır. Bugünkü arama motorları çok daha fazlasını hesaba katıyor olsa da, bağlantıların matematiğini görünür kılan bu fikir ağ biliminin temel taşlarından biri olarak kalıyor.