İçeriğe atla
Arama sonuçlarına dön

PageRank Merkezi̇li̇ği̇

Ortaya koyan
Page, Brin, Motwani & Winograd
Yıl
1999
Tür
Iterative link-based centrality algorithm
Aile
Centrality

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

PageRank, yönlendirilmiş bir grafikteki her bir düğüme, ona bağlanan yüksek kaliteli düğümlerin sayısını ölçerek bir önem puanı atayan, bağlantı tabanlı bir merkezi̇li̇k algoritmasıdır.

Larry Page, Sergey Brin, Rajeev Motwani ve Terry Winograd tarafından 1999 yılında Stanford Üniversitesi'nde tanıtılan bu algoritma, Google arama motorunun matematiksel temeli haline gelmiş ve ağ bilimi ile bilgi erişiminde en etkili algoritmalardan biri olmaya devam etmektedir.

Yöntemin mantığı

Rastgele bağlantıları tıklayan, ara sıra bir bağlantıyı takip etmek yerine tamamen rastgele bir sayfaya atlayan rastgele bir web sörfçüsü hayal edin. Bu sörfçünün her sayfada geçirdiği sürenin kesri, sonsuz sayıda tıklamadan sonra, o sayfanın PageRank'idir. Çok popüler sayfalar ona bağlandığı için sık ziyaret edilen bir sayfa yüksek bir puan alır. Sönümleme faktörü (tipik olarak 0.85), atlamak yerine tıklamaya devam etme olasılığını modeller.

Tarih

PageRank, Stanford Üniversitesi'nde Larry Page ve Sergey Brin tarafından BackRub arama projesinin temel sıralama mekanizması olarak geliştirilmiştir ve bu proje 1998'de Google olmuştur. Rajeev Motwani ve Terry Winograd ile birlikte yazılan temel teknik rapor 1999'da yayınlanmıştır. Algoritma, büyük ölçekli yönlendirilmiş ağlarda özvektör tabanlı merkezi̇li̇k kullanımını popülerleştirmiş ve HITS ve TrustRank dahil olmak üzere sonraki bağlantı analizi algoritmalarına doğrudan ilham vermiştir.

Ne zaman kullanılır?

PageRank, özellikle kenar yönünün onay veya etkiyi (köprüler, alıntılar, sosyal takipler) kodladığı durumlarda, yönlendirilmiş bir grafikteki düğümleri küresel yapısal önemine göre sıralamanız gerektiğinde uygundur. Grafiğin bir Markov zinciri olarak modellenebileceğini varsayar ve temiz yakınsama için bağlı veya güçlü bağlı bir bileşen gerektirir. Yönsüz ağlar için daha az uygundur, bu ağlarda HITS veya ara merkezi̇li̇k tercih edilebilir ve bağlantı spam'ine veya yapay olarak şişirilmiş gelen dereceye duyarlı olabilir.

Sınırlar ve dikkat edilmesi gerekenler

  • Yönlendirilmiş bir grafik gerektirir; yönsüz ağlara uygulama, seçim kararları gerektirir
  • Yakınsama hızı, geçiş matrisinin spektral aralığına bağlıdır ve kötü bağlı grafikler için yavaş olabilir
  • Sönümleme faktörü d'nin seçimine duyarlıdır; farklı değerler sıralamaları önemli ölçüde değiştirebilir
  • Bağlantı çiftliği manipülasyonuna ve yapay olarak oluşturulmuş gelen bağlantılara karşı savunmasızdır

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Rastgele sörfçü Markov zinciri modeli aracılığıyla prensipli olasılıksal temel
  • Seyrek matris-vektör çarpımları ve kuvvet yinelemesi yoluyla çok büyük grafiklere ölçeklenir
  • Küresel grafik topolojisini yakalar, diğer yüksek puanlı düğümler tarafından onaylanan düğümleri ödüllendirir
  • Web, atıf, biyolojik ve sosyal ağ alanlarında yaygın olarak doğrulanmıştır

Uygulama alanları

  • Web arama motoru sıralaması: arama sonuçlarını web sayfalarının küresel otoritesine göre sıralama
  • Akademik atıf analizi: bilimsel literatür ağlarında etkili makaleleri veya dergileri belirleme
  • Sosyal ağ etki ölçümü: kullanıcıları takipçilerinin prestijine göre sıralama
  • Biyolojik ağ analizi: protein-etkileşim ve gen-düzenleyici ağlarda anahtar proteinleri veya genleri bulma
  • Öneri sistemleri: kullanıcı-öğe çift yönlü grafikler aracılığıyla tercih sinyallerini yayma

Nasıl çalışır?

Nasıl çalışır?

1

Grafikteki her düğüm, N toplam düğüm sayısı olmak üzere 1/N eşit PageRank puanıyla başlar. Bu tekdüze başlatma, hiçbir düğümün yapay bir başlangıç avantajına sahip olmamasını sağlar ve ilk yinelemeden önce ağ genelinde geçerli bir olasılık dağılımı sağlar.

Formül
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}
2

Grafiğin komşuluk yapısından bir sütun-stokastik geçiş matrisi M oluşturulur. M_ij girdisi, j'den i'ye bir kenar varsa 1 bölü j'nin dış derece'sine eşittir, aksi takdirde sıfırdır. Asılı düğümler (giden kenarı olmayanlar) tipik olarak puanlarını tüm düğümlere tekdüze olarak yeniden dağıtarak ele alınır.

Formül
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}
3

PageRank vektörü, rastgele sörfçü formülü kullanılarak iteratif olarak güncellenir. Sönümleme faktörü d (varsayılan 0.85) ile her düğüm, temel bir ışınlanma olasılığı (1-d)/N artı, ona bağlanan tüm düğümlerden gelen puanların ağırlıklı toplamının d katını alır. Bu adım, puanlar stabilize olana kadar tekrarlanır.

Formül
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}
4

Her yinelemeden sonra, puan vektöründeki değişimin L1 normu, küçük bir tolerans epsilon (örneğin, 1e-6) ile karşılaştırılır. Değişim bu eşiğin altına düştüğünde, algoritma yakınsamış demektir ve mevcut puan vektörü nihai PageRank dağılımı olarak döndürülür.

Formül
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilon

Sık yapılan hatalar

  • Asılı düğümleri (giden kenarı olmayan düğümler) göz ardı etmek, geçiş matrisinin stokastik özelliğini bozabilir ve yanlış puanlara neden olabilir
  • Yönsüz grafiklerde PageRank kullanmak, simetrik bir geçiş modeline dönüştürmeden, yanıltıcı merkezi̇li̇k tahminleri üretebilir
  • Toleransı çok gevşek ayarlamak erken yakınsamaya yol açar; çok sıkı ayarlamak, anlamlı puan değişiklikleri olmadan hesaplamayı artırır
  • PageRank'i belirli bir grafik bağlamındaki göreceli bir sıralama yerine mutlak bir önem metriği olarak yorumlamak

Sık sorulan sorular

Sönümleme faktörü d neyi temsil eder ve nasıl seçilmelidir?

Sönümleme faktörü d (tipik olarak 0.85), rastgele sörfçünün rastgele bir düğüme ışınlanmak yerine bir bağlantıyı takip etme olasılığıdır. 1'e yakın değerler algoritmayı grafik yapısına daha duyarlı hale getirir ancak yakınsamayı yavaşlatır ve sıralama bataklıklarına daha yatkın hale getirir; 0'a yakın değerler tekdüze sıralamaya yaklaşır. 0.85 değeri Page ve Brin tarafından web grafiği için ampirik olarak doğrulanmış ve standart varsayılan değerdir.

PageRank, derece merkezi̇li̇ği̇nden nasıl farklıdır?

Derece merkezi̇li̇ği̇, yalnızca bir düğüme gelen doğrudan bağlantı sayısını sayar ve tüm kaynakları eşit kabul eder. PageRank, her gelen bağlantıyı bağlanan düğümün puanıyla ağırlıklandırır, bu nedenle yüksek puanlı bir düğümden gelen bir onay, düşük puanlı bir düğümden gelen bir onaydan daha fazla katkıda bulunur. Bu özyinelemeli tanım, yalnızca yerel bağlantı yerine küresel grafik yapısını yakalar.

PageRank yönsüz grafiklere uygulanabilir mi?

Evet, ancak bazı uyarılarla. Yönsüz bir grafik, her yönsüz kenarı iki yönlü kenarla değiştirerek yönlendirilmiş bir temsile dönüştürülmelidir. Elde edilen PageRank puanları daha sonra düğüm derecesinin bir fonksiyonuna eşit olur ve algoritmayı ağırlıklı derece merkezi̇li̇ği̇ne indirger. Yönsüz ağlar için, özvektör merkezi̇li̇ği̇ veya ara merkezi̇li̇ği̇ gibi alternatif merkezi̇li̇k ölçümleri genellikle daha bilgilendiricidir.

İlgili yöntemler

Kaynaklar

  1. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.

    Yayın kaynağını aç
    Kopyalandı.