Link Analizi: Pagerank II

Bir önceki yazımda size ünlü PageRank algoritmasının doğuşunu ve arama motorlarının gelişimini kısa bir şekilde anlatmaya çalıştım. Bu yazımda ise sizi algoritmanın tanımı ve ağ yapısı konusunda elimden geldiğince bilgilendirmeye çalışacağım. Birazcık graph theory (graf teorisi) ve lineer cebir bilgisiyle bu konuyu çok kolay anlayabileceğinizi düşünüyorum. Fakat bu konular hakkında hiç bilgi sahibi değilseniz, öncesinde bunlara dair bir şeyler okumanızı öneririm.
Ağ’ın graph yapısı

Eğer ağ sayfalarını node(düğüm), sayfalar arasındaki bağlantıları edge(kenar) olarak düşünürseniz, ağ yapısının belki de görebileceğimiz en büyüleyici ve en karmaşık graphlardan biri olduğunu fark edeceksiniz. Böyle büyük bir yapıyı size daha kolay bir biçimde anlatabilmek için graph yapısını, basitleştirilmiş bir graph üzerinden anlatacağım.
Tesadüfi hareket teorisi (Random Walk Theorem)

Bir cumartesi akşamı çok sıkıldınız, yapacak hiçbir şeyiniz yok. Arkadaşlarınızla buluşacaktınız ama nedeni bilinmeyen bir şekilde planınız son dakikada iptal oldu. Üstünüzde pijamalarınız, elinizde kahveniz ile bilgisayarın başına oturdunuz. Web’i yan taraftaki graph gibi düşünün. Bu sizin sadece 5 sayfadan oluşan Küçük Web’iniz olsun. Tarayıcı size bu 5 sayfayı listeliyor ve siz rastgele bir tanesine tıklıyorsunuz. Diyelim ki A sayfasına tıkladınız. A sayfasından gidebileceğiniz 2 sayfa var: B ve D. Bir sonraki sayfaya geçmek istediğinizde ya 1/2 ihtimalle B’ye ya da 1/2 ihtimalle A’ya gideceksiniz. Eğer B’ye giderseniz, bir sonraki adımda yine 1/2 ihtimalle C ya da A sayfasına gideceksiniz. Eğer D’ye giderseniz, üçüncü adımda 1/3 ihtimalle C, B ya da E sayfasında olacaksınız. Bu şekilde hareketiniz devam edecek.
Şimdi, eğer Küçük Web’imizde bir adım sonra hangi sayfada olabileceğimizin olasılık değerlerini M adlı bir matriste tutsaydık, M aşağıdaki gibi olurdu:

Biz bu matrise transition matrix (geçiş matrisi) diyoruz. Satırlar ve sütunlar sırasıyla A, B, C, D, E sayfalarını temsil ediyor. Örneğin son sütunu baz alırsak E sayfasından 1/2 ihtimalle A’ya ya da C’ye gidilebileceğini görebilirsiniz. Olasılık değeri bu iki sayfaya dağılmıştır (1/2=0.5). Aynı şekilde D sayfasından B,C ve E sayfalarına 1/3=0.33 oranında dağıldığını görebilirsiniz.
Sizi bilgisayar başında unuttuk, hadi başa dönelim. Tarayıcıyı açtınız ve gidebileceğiniz 5 sayfa var. Eğer başlangıçtaki olasılık dağılımı v adlı bir vektör ile tanımlansaydı, ilk olarak herhangi bir sayfada başlama ihtimaliniz 1/5=0.2 olduğundan v şu şekilde olurdu:

Bir sayfadan diğerine geçmeye başladınız. Her node’dan bir diğerine geçiş ihtimaliniz M olarak tanımlandığı için, ilk adımdan sonra bir node’da olma ihtimalinizi belirten v vektörü Mv olarak değişecektir. İkinci adımdan sonra vektör M(Mv), i’nci adımdan sonra (M^i)v olacaktır. Bu basit bir Markov prosesidir, vektör değerleri belli bir adımdan sonra kayda değer bir değişim göstermemeye başlar ve yaklaşık bir değer edinir:

Maalesef, mevcut ağ yapısı bizim Küçük Web’imizden daha karmaşıktır. Öncelikle graph bu denli strongly connected değildir. Bir graph’ın strongly connected olması her node’un bir diğer node’dan en az bir yol ile ulaşılabilir olmasıdır. Gerçek ağ yapısı şu şekilde tanımlanabilir:
Ağ yapısı aşağıdaki graph gibidir ve bileşenleri şu şekildedir:
- P1: Sayfaların strongly connected olduğu graph bileşenleri
- P2: P1'e doğru bağlantısı olan ama P1’den ulaşılamayan graph bileşenleri
- P3: P1'den ulaşılabilinen fakat P1'e doğru bağlantısı olmayan graph bileşenleri
- P4: P2'den ulaşılabilinen fakat P2'ye doğru bağlantısı olmayan graph bileşenleri
- P5: P3'ten ulaşılamayan ama P3'e doğru bağlantısı olan graph bileşenleri
- P6: P2'den ulaşılabilinen, P3'e doğru bağlantısı olan fakat P1 ile direkt bağlantısı bulunmayan graph bileşenleri
- P7: Bağlantısız graph bileşenleri

Markov prosesi böyle bir graph’a uygulanamaz. Mesela P7'den diğer bileşenlere gidemediğiniz gibi P4'ten herhangi bir bileşene gitme ihtimaliniz yoktur. Dolayısıyla birçok kez sayfadan sayfaya rastgele geçişler yaptığınız takdirde, nihayetinde ya P3'te veya P4'te olacaksınız ya da P7'den dışarı hiç çıkamayacaksınız. Bu PageRank değerlerinin yanlış hesaplanmasına yol açar, çünkü bir sayfanın PageRank değeri sizin gibi sayfadan sayfaya geçiş yapan kişilerin o sayfada bulunma yüzdesine göre hesaplanır. Bu durum P1,P2,P6 ve P5'in PageRank değerlerinin eninde sonunda sıfırlanması anlamına gelir.
Ağ yapısında PageRank değerlerinin yanlış hesaplanmasına sebep olan iki ana sorun şu şekildedir:
- Dead end’ler (Çıkmazlar): Dışarıya bağlantısı olmayan nodelar.
- Spider Trap’ler (Örümcek Tuzağı): Grup içinden grup dışı bağlantıya sahip olmayan sayfa kümeleri.
Bu problemler serinin 3. yazısının konusu olacak Taxation diye bir yöntem ile çözülebilir.
Not: Bu seri Bilkent Üniversitesi’nde aldığım “Algorithms for Web-Scale Data” dersinde öğrendiğim konuların ufak bir kısmıdır. PageRank algoritması ilgimi çektiği için ve algoritmanın ufuk açıcı bir yapısı olduğundan dolayı, öğrendiklerimin bir kısmını sizinle paylaşmak istedim. Dersin orijinal içeriği daha kapsamlı bir şekilde şu adreste bulunabilir. Bu bağlantıda derse ait her türlü materyal bulunmaktadır. İngilizceniz varsa ve bu konularla ilgiliyseniz bu sayfadan öğrenmeye devam etmenizi şiddetle tavsiye ederim. Teşekkürler.
Kaynaklar:
Jure Leskovec, Anand Rajaraman, Jeff Ullman. “Mining of Massive Datasets”

