Link Analizi: PageRank III

Bu serinin ikinci kısmında sizinle PageRank değerlerinin nasıl hesaplandığını ve Random-Walk algoritmasının işleyini paylaşmıştım. Sonrasında, PageRank değerlerinin yanlış hesaplanmasına yol açan iki ana problemden kısaca bahsetmiştim. Bu serinin üçüncü ve son kısmında size bu problemleri ve bu problemlerin çözüm yöntemi olan taxation metodunu anlatacağım.

Öncelikle bu problemlerin ne olduğunu hatırlayalım:

Dead Ends:

Dead end’ler kısaca dışarıya bağlantısı olmayan node’lardır. Eğer Web üzerinde rastgele geziniyorsanız ve hasbelkader dead end’lerden birine geldiyseniz, o sayfa dışarıya bağlantı vermediğinden daha sonra başka bir sayfaya geçme imkanınız olmayacaktır. O sayfada sıkışıp kaldığınız için, sizin ve sizin gibi rastgele Web’i dolanan kişilerin diğer sayfalarda bulunma ihtimalleri bir noktadan sonra sıfırlanacaktır.

Eğer bu dediğim size anlamsız geldiyse, aşağıdaki örneği inceleyelim:

Dead end’e sahip bir graph

Ağ yapımızın yukarıdaki gibi olduğunu varsayalım. Görebileceğiniz üzere, E sayfası dışarı giden herhangi bir bağlantıya sahip değil, yani E bir dead end. İkinci yazıda bahsettiğimiz gibi bu graph’ın geçiş matrisini hesaplarsak, aşağıdaki matrisi elde ederiz:

Yine ikinci yazıda yaptığımız gibi, rastgele dolaşan kişinin n adım sonra sayfaların herhangi birinde bulunma ihtimalinin vektörünü hesaplarsak aşağıdaki sonucu elde ederiz:

Bu hesaplamadan sonuç çıkardığımızda n adım sonra rastgele dolaşan kişinin herhangi bir sayfada bulunma ihtimalinin sıfırlandığını görüyoruz. Matematiksel anlamı dışında, dead end üzerinde bulunan birinin bir sonraki adımda herhangi bir sayfaya gidebilme ihtimalinin 0 olduğunu rahatlıkla görebiliriz. Bu, sayfaların PageRank değerlerinin yanlış hesaplanmasına sebep olur çünkü, değerler eninde sonunda sıfırlanır.

Dead End’lerle başa çıkmak:

Dead end problemini çözmenin iki basit yolu vardır:

1. Dead End’leri silmek: Bu işlem dead end olan sayfaların kendilerinin ve onlara gelen bütün bağlantıların silinmesi işlemidir. Dead end’lerin silinmesi yeni dead end’lerin ortaya çıkmasına sebebiyet verebilir. Bu nedenle aynı prosedüre dead end kalmayana dek devam edilir.
2. Taxation: Spider trap başlığından sonra bu yöntemden bahsedeceğim.

Spider Traps:

Spider trap’leri bir veya birden fazla sayfanın sadece birbirlerine link vermesinden dolayı oluşur. Bu yapıyı dead end’in büyük bir versiyonu gibi düşünebilirsiniz. Bu sefer bir sayfada değil birçok sayfadan oluşabilen bir grupta sıkışmışsınızdır. Bu durum PageRank değerlerinin sadece spider trap’i oluşturan sayfalara dağıtılmasına sebebiyet verir. Spider trap dışındaki sayfaların PageRank değerleri n adım sonrasında spider trap içindeki sayfalara dağılacaktır.

Spider trap’li bir graph

Bu spider trap’in olabileceği en basit formdur. Tek bir sayfadan oluşmaktadır. Graph’a baktığınızda E sayfasının kendinden başka bir sayfaya bağlantı göndermediğini görebilirsiniz, dolayısıyla E sayfasına gittiğinizde bir sonraki adımda gidebileceğiniz tek sayfa yine E olacaktır. Rastgele gezinen birinin n adım sonunda bulunacağı sayfanın E olduğu düşünülünce, diğer bütün sayfaların PageRank değerinin sıfırlanacağı ve herkesin bir sonraki adımda E sayfasında bulunacağı öngörülebilir. Diğer bir deyişle PageRank değerinin tamamı spider trap içinde dağılacak ve diğerlerinin PageRank değeri sıfır olacaktır.

Yukarıdaki graph’ın geçiş matrisi şekildeki gibidir:

Rastegele gezen birinin n adım sonra sayfalarda bulunma ihtimalini gösteren vektör v ise şu şekilde değişime uğramaktadır:

Not: Eğer bu hesaplamanın nasıl yapıldığını hatırlamıyorsanız serinin 2. yazısına tekrar göz atmanızı öneririm.

Yukarıdaki tabloya baktığımızda n adım sonra rastgele gezen kişinin E dışında bir sayfada bulunma ihtimalinin 0 olduğunu görürsünüz.

Web’i PageRank ile analiz etmeye çalışırken bu değerler olmasını istediğimiz değerler değildir. Bütün PageRank değerinin bir sayfada bulunmasını istemeyiz. Spider trap ve dead end problemini çözmek için taxation adlı yöntemi kullanabiliriz.

Taxation

Bu iki problemin doğasını incelediğimizde ve ikisinin ortak paydasını aradığımızda şu durumla karşılaşırız:

Dead end probleminde sorunumuz değerlerin sıfırlanması iken, spider trap’te problemimiz değerlerin spider trap içerisinde sıkışıp kalmasıdır. Bu iki sorunun ortak yönü dead end’in de spider trap’in de herhangi bir çıkış yolu olmamasıdır. Dolayısıyla bulabileceğimiz en kolay çözüm dead end ve spider trap’lere bir çıkış opsiyonu eklemektir.

Formülü yeniden yapılandırıp, rastgele gezen kişilere giden bağlantıları takip etmek yerine rastgele bir sayfaya sıçrama olasılığı verdiğinizde şu sonucu elde edeceksiniz:

Daha önceden rastgele gezen birinin bir sonraki adımda graph’taki sayfalarda bulunma olasılıklarını gösteren formül soldaki iken, yeni formülümüz sağdaki gibidir. ß önceden belirlenmiş bir olasılık değeriyken, e 1'lerden oluşan uygun boyutta bir vektör ve n graph’ta bulunan sayfaların sayısıdır. Dolayısıyla formülün ilk kısmı ßMv, bulunduğumuz sayfadan dışarıya giden bağlantıları takip etme olasılığımızken, geriye kalan kısmı bir sonraki adımda rastgele bir sayfaya sıçrama olasılığımızdır.

Eğer bu formülü yukarıdaki spider trap içeren graph’a, ß=0.8 değeriyle uygularsak, aşağıdaki iterasyon formülünü elde ederiz:

Modifiye edilmiş formülün üstteki graph’a uygulanmış hali

Yukarıdaki formül uygulandığında, rastgele gezen birinin n adım sonra bu sayfalarda bulunma olasılığının değişimi şu şekilde seyreder:

Sonuç olarak, yine olasılık dağılımının büyük çoğunluğu E sayfasına kalsa da, her sayfa için sıfır olmayan bir değer elde etmeyi başarmış oluruz. Böylece sayfaların PageRank değerlerini hesaplayabiliriz.

Bu yaklaşımla gördüğünüz gibi yukarıda bahsettiğimiz iki problemi de çözebildik ve bu serinin sonuna geldik. Eğer yorumunuz, ekleme/çıkarma yapmak istediğiniz bir yer varsa, lütfen aşağıdan bildiriniz. Okuduğunuz için teşekkürler!

Kaynak:

Jure Leskovec, Anand Rajaraman, Jeff Ullman. “Mining of Massive Datasets”