PageRank ve HITS Algoritmaları
PageRank ve HITS, web sayfalarının önemini veya yetkinliğini yalnızca sayfa içeriğinden ziyade köprü grafiğinin yapısından tahmin eden bağlantı analizi algoritmalarıdır.
Tanım
PageRank, her sayfaya, dış bağlantıları belirli bir sönümleme olasılığıyla takip eden ve aksi takdirde ışınlanan (teleport) rastgele bir sörfçü altında durağan olasılığına eşit, sorgudan bağımsız bir önem puanı atamaktadır; HITS ise, sorguya bağımlı bir alt grafik için, değerli içeriğe sahip sayfalar için yetki puanları ve iyi yetkililere bağlantı veren sayfalar için merkez (hub) puanları hesaplamakta ve bu puanlar birbirini karşılıklı olarak güçlendirmektedir.
Kapsam
Bu konu, iki temel bağlantı analizi algoritmasını ele almaktadır: teleportasyonlu rastgele sörfçü modeline dayalı, sorgudan bağımsız bir sayfa önemi ölçütü olan PageRank ve karşılıklı olarak güçlendiren merkez (hub) ve yetki (authority) puanlarını hesaplayan, sorguya bağımlı bir yöntem olan HITS. Temelindeki rastgele yürüyüş ve özvektör formülasyonlarını, sönümleme (damping) ve teleportasyonun rolünü, yakınsamayı ve konuya duyarlı varyantları incelemektedir. Bu puanların metin özellikleriyle birleştirilerek nihai bir sıralama oluşturulmasının web arama sıralamasına ait olması nedeniyle bu kapsam dışında bırakılmıştır.
Temel sorular
- Rastgele sörfçü modeli, PageRank'i durağan bir dağılım olarak nasıl tanımlamaktadır?
- PageRank'in iyi tanımlanabilmesi için neden bir sönümleme veya teleportasyon faktörüne ihtiyaç duyulmaktadır?
- HITS'teki merkez (hub) ve yetki (authority) puanları birbirini nasıl güçlendirmektedir?
- Bu puanlar yinelemeli olarak nasıl hesaplanmakta ve ne zaman yakınsamaktadır?
- PageRank ve HITS, sorgudan bağımsız olma ve sorguya bağımlı olma açısından nasıl farklılaşmaktadır?
Anahtar kavramlar
- PageRank
- rastgele sörfçü modeli
- sönümleme faktörü ve teleportasyon
- durağan dağılım / ana özvektör
- HITS
- merkezler (hubs) ve yetkililer (authorities)
- sorgudan bağımsız ve sorguya bağımlı puanlama
- kuvvet yinelemesi (power iteration) ve yakınsama
Temel kuramlar
- PageRank rastgele sörfçü modeli
- Bağlantıları sönümleme faktörüne eşit bir olasılıkla takip eden ve aksi takdirde rastgele bir sayfaya atlayan bir sörfçüyü modellemek, benzersiz durağan dağılımı sayfaları uzun vadeli ziyaretlere göre puanlayan, istikrarlı, sorgudan bağımsız bir önem ölçütü sağlayan bir Markov zinciri üretmektedir.
- HITS merkezleri (hubs) ve yetkilileri (authorities)
- Sorgu odaklı bir alt grafik içinde, HITS her sayfaya, kendisine bağlantı veren sayfaların merkez (hub) puanlarıyla orantılı bir yetki (authority) puanı ve bağlantı verdiği sayfaların yetki puanlarıyla orantılı bir merkez (hub) puanı atamakta olup, bu puanlar karşılıklı olarak güçlendiren ilişkilerin yakınsamaya kadar yinelenmesiyle hesaplanmaktadır.
Klinik önem
PageRank, büyük ölçekli web aramasının yükselişinde merkezi bir rol oynamış ve grafikler üzerindeki önem ve yetki için kavramsal bir referans noktası olmaya devam etmektedir. Bağlantı analizi fikirleri, web'in ötesine geçerek atıf ağlarına, sosyal ağ etkisine, dolandırıcılık tespitine ve tavsiye sistemlerine, yani onay benzeri bağlantıların bilgi taşıdığı her alana genellenebilmektedir.
Tarihçe
1998 ve 1999 yıllarında, neredeyse eş zamanlı iki öneri, köprülerin yetkiyi kodladığını göstermiştir: Kleinberg'in HITS'i ile Page ve Brin'in PageRank'i. PageRank'in sorgudan bağımsız, küresel olarak hesaplanan puanları, web ölçeğinde hizmet vermeye oldukça uygun olduğunu kanıtlamış ve önde gelen bir arama motorunun temelini oluşturmuştur; HITS ise konu damıtma (topic-distillation) ve daha sonraki grafik sıralama araştırmalarını etkilemiştir.
Öne çıkan isimler
- Larry Page
- Sergey Brin
- Jon Kleinberg
- Rajeev Motwani
İlgili konular
Temel eserler
- page1999
- kleinberg1999
- brin1998
Sıkça sorulan sorular
- PageRank ve HITS arasındaki fark nedir?
- PageRank, tüm web grafiğinden her sayfa için önceden tek bir sorgudan bağımsız önem puanı hesaplamaktadır; HITS ise, sorgulama anında sorgu etrafında oluşturulan küçük bir alt grafik üzerinde sorguya bağımlı merkez (hub) ve yetki (authority) puanları hesaplamaktadır. PageRank, web hizmetine daha kolay ölçeklenebilmektedir.
- PageRank neden bir sönümleme faktörüne ihtiyaç duymaktadır?
- Bu faktör olmadan, rastgele sörfçü dış bağlantısı olmayan sayfalarda veya döngülerde sıkışıp kalabilmekte ve durağan dağılım benzersiz veya iyi tanımlanmış olmayabilmektedir. Sönümleme (teleportasyon) olasılığı, sörfçünün ara sıra rastgele bir sayfaya atlamasına izin vererek, benzersiz ve iyi davranışlı bir puanı garanti etmektedir.