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

Weighted PageRank (Ağırlıklı Sayfa Sıralaması)

Ortaya koyan
Xing, W. & Ghorbani, A.
Yıl
2004
Tür
Centrality measure / ranking algorithm
Aile
Network science

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

Yazı boyutu

Ne işe yarar?

Weighted PageRank, klasik PageRank algoritmasını, kenarların farklı güçlere veya frekanslara sahip olduğu ağlara genişleterek, önemi yalnızca gelen ve giden kenar ağırlıklarına orantılı olarak dağıtır; ikili PageRank'in aksine tüm bağlantıları eşit kabul etmez.

Bu, bağlantı gücünün önemli olduğu her ağda onu ikili PageRank'ten önemli ölçüde daha bilgilendirici hale getirir.

Yöntemin mantığı

Klasik PageRank, her köprü veya bağlantıyı aynı şekilde ele alır: bir düğüm, zayıf bir bağlantıdan güçlü bir bağlantı kadar eşit prestij kazanır. Weighted PageRank, her oyu kenarın göreceli ağırlığıyla ölçeklendirerek bunu düzeltir. Zaten önemli düğümlerden çok sayıda ağır ağırlıklı gelen bağlantı alan bir düğüm sıralamada en üste tırmanırken, çok sayıda ancak zayıf bağlantısı olan bir düğüm mütevazı kalır. Bu, etkileşimin sıklığı veya işlem hacminin gerçek önemi gösterdiği çoğu gerçek dünya ağında etkinin aslında nasıl biriktiğini yansıtır.

Tarih

PageRank, 1998'de Brin ve Page tarafından Google Arama'nın temeli olarak tanıtıldı ve tüm köprüleri eşit oylar olarak ele aldı. Weighted PageRank, 2004'te Xing ve Ghorbani tarafından resmileştirildi, algoritmayı kenar ağırlıklarına orantılı olarak sıralama dağılımı atamak üzere genişletti ve gelen ve giden ağırlık kesirlerine dayandı. O zamandan beri, bağlantı gücünün etki için anlamlı bir vekil olduğu atıf analizi, biyoinformatik, sosyal ağ analizi ve öneri sistemlerinde uygulanmıştır.

Ne zaman kullanılır?

Ağınızın anlamlı kenar ağırlıklarına sahip olduğu ve düğümlerin küresel, akışa duyarlı bir önem sıralamasına ihtiyaç duyduğunuzda Weighted PageRank'i kullanın. Bu, ortak atıf sayılarına sahip atıf ağları, trafik hacimlerine sahip web grafikleri, ifade seviyelerine sahip biyolojik etkileşim ağları, etkileşim frekanslarına sahip sosyal ağlar ve finansal işlem ağları için idealdir. Kenar gücünü göz ardı etmenin etki akışını yanlış temsil edeceği durumlarda ikili PageRank yerine Weighted PageRank'i tercih edin. Kenar ağırlıklarının güvenilmez veya rastgele atandığı, ağın çok seyrek olduğu ve ağırlıkların çoğunlukla ikili olduğu (normal PageRank yeterlidir) veya ağırlıklı derece gibi yalnızca yerel bir merkeziyet ölçüsüne ihtiyaç duyduğunuz durumlarda bundan kaçının. Kavramsal olarak akış yönünün anlamsız olduğu yönsüz ağlar için uygun değildir.

Sınırlar ve dikkat edilmesi gerekenler

  • Kenar ağırlıklarının anlamlı ve güvenilir bir şekilde ölçülmesini gerektirir; gürültülü veya rastgele ağırlıklar sıralama kalitesini düşürür.
  • Sönümleme faktörü (d) serbest bir parametredir; web dışı ağlar için geleneksel 0.85 değeri en uygun olmayabilir.
  • Seçilen ağırlık normalleştirme şemasına duyarlıdır; gelen ve giden ağırlıklar farklı bir şekilde birleştirilirse sonuçlar farklılık gösterebilir.
  • Farklı kenar türleri arasında ayrım yapmaz; tek ağırlıklı bir model önemli yapısal ayrımları ortadan kaldırabilir.
  • Verimli seyrek matris uygulamaları olmadan çok büyük, yoğun ağlarda yakınsama yavaş olabilir.

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

Güçlü yönleri

  • Önem yayılımına kenar gücünü doğrudan dahil ederek, ağırlıklı ağlarda ikili PageRank'ten daha gerçekçi sıralamalar sağlar.
  • Yalnızca yerel bağlantıyı değil, küresel, ağ çapında prestiji yakalar.
  • PageRank'in ışınlama mekanizmasını koruyarak, düzeltildiğinde sarkan düğümlere ve bağlantısız bileşenlere karşı dayanıklı olmasını sağlar.
  • Verimli iteratif hesaplama yoluyla büyük ağlara ölçeklenir; seyrek matris işlemleri belleği yönetilebilir tutar.
  • Kolayca yorumlanabilir: yüksek bir puan, bir düğümün diğer yüksek puanlı düğümlerden ağır, ağırlıklı onay aldığını gösterir.

Uygulama alanları

  • Ağırlıklı atıf ve ortak atıf ağlarında etkili makaleleri veya yazarları belirlemek.
  • Köprü trafiği hacmi veya tıklama oranlarının mevcut olduğu web sayfalarını veya belgeleri sıralamak.
  • Ağırlıklı biyolojik etkileşim ağlarında anahtar proteinleri veya genleri tespit etmek.
  • İşlem hacmi akışına göre finansal işlem ağlarındaki düğümleri önceliklendirmek.
  • Ağırlıklı sosyal medya etkileşim grafiklerinde kullanıcıları veya içeriği sıralamak.
  • Öğe ortak oluşum frekanslarının kenar ağırlıkları olarak hizmet ettiği öneri sistemleri oluşturmak.

Nasıl çalışır?

Nasıl çalışır?

1

Ağı, her kenarın bağlantı gücünü yansıtan sayısal bir ağırlığa sahip olduğu bir grafik olarak temsil edin — örneğin etkileşim sıklığı, işlem hacmi, ortak yazarlık sayısı veya benzerlik puanı. Algoritma, bu ağırlıkların negatif olmamasını gerektirir; negatif ağırlıklar analizden önce dönüştürülmelidir.

2

Her bir v'den u'ya giden yönlü kenar için iki ağırlık faktörü hesaplayın: u'nun toplam gelen ağırlığına göre kenar ağırlığını normalleştiren bir gelen ağırlık faktörü ve v'nin toplam giden ağırlığına göre normalleştiren bir giden ağırlık faktörü. Bu kesirler, v'nin sıralamasının bu özel kenar aracılığıyla u'ya ne kadarının dağıtılacağını belirler.

Formül
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}
3

Weighted PageRank formülünü iteratif olarak uygulayın: her düğümün sıralaması, temel bir ışınlama terimi (1 eksi sönümleme faktörü d, tipik olarak 0.85) artı d çarpı, tüm gelen komşulardan gelen sıralamalarının iki ağırlık faktörüyle ölçeklendirilmiş toplamıdır. Bu, sıralamayı düzgün bir şekilde değil, kenar gücüne orantılı olarak dağıtır.

Formül
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)
4

Her düğümün puanındaki değişiklik küçük bir toleransın (genellikle 1e-6) altına düşene kadar sıralama güncellemesini tekrarlayın. Güçlü bağlı grafikler için yakınsama garanti edilir; sarkan düğümlere veya izole bileşenlere sahip grafikler için, yinelemeden önce standart sarkan düğüm düzeltmesini uygulayın.

5

Puanlar yakınsandıktan sonra, tüm düğümleri Weighted PageRank puanlarına göre azalan sırada sıralayın. Bu sıralamalar, hem ağ topolojisini hem de kenar gücünü hesaba katan her düğümün küresel yapısal önemini yansıtır.

Sık yapılan hatalar

  • Ölçeklerinin kontrol edilmeden ham, normalleştirilmemiş kenar ağırlıklarının kullanılması — onlarca olan sayıları milyonlarca olan değerlerle karıştırmak sıralama yayılımını bozar.
  • Ağın tamamından sıralama çekebilecek sarkan düğümlerin (giden kenarı olmayan düğümler) işlenmemesi varsayımı, eğer düzeltilmezse.
  • Varsayılan sönümleme faktörü olan 0.85'in evrensel olarak uygun olduğunu varsaymak; atıf veya biyolojik ağlarda farklı bir değer alanın daha iyi yansıtılması.
  • Weighted PageRank puanlarını mutlak olasılıklar olarak yorumlamak yerine göreceli sıralamalar olarak — yalnızca sıraları farklı çalıştırmalar arasında kararlıdır.
  • Normalleştirme olmaksızın farklı boyutlardaki ağlar arasındaki Weighted PageRank puanlarını karşılaştırmak.

Sık sorulan sorular

Weighted PageRank, standart PageRank'ten nasıl farklıdır?

Standart PageRank, bir düğümün sıralamasını kenar gücünden bağımsız olarak tüm giden komşularına eşit olarak dağıtır. Weighted PageRank, bu dağılımı her kenarın göreceli gelen ve giden ağırlığına göre ölçeklendirir, böylece daha güçlü bağlantılar orantılı olarak daha fazla sıralama taşır.

Hangi sönümleme faktörü kullanılmalıdır?

Geleneksel değer 0.85'tir, bu değer rastgele sörf varsayımlarına dayanan web grafiğinden türetilmiştir. Sosyal, biyolojik veya atıf ağları için, literatürde 0.5 ile 0.9 arasındaki değerler araştırılmaktadır. Bir dizi sönümleme değeri üzerinde hassasiyet analizi önerilir.

Weighted PageRank yönsüz ağlara uygulanabilir mi?

Evet, her yönsüz kenarı aynı ağırlığa sahip bir çift yönlü kenar olarak temsil ederek. Algoritma daha sonra simetrik gelen ve giden ağırlık faktörleri üretir, bu da kenar gücünü hala dikkate alan bir formüle basitleşir.

Sıfır ağırlıklı kenarlar nasıl ele alınır?

Sıfır ağırlıklı kenarlar sıralama yayılımına hiçbir katkıda bulunmaz, bu nedenle analizden önce kaldırılabilirler. Sıfır ağırlıklar yapısal olarak anlamlıysa (eksiklik yerine eksik veri), kaldırmadan önce ayrımı açıkça belgeleyin.

Weighted PageRank, ağırlıklı derece merkeziyetinden daha mı iyidir?

Araştırma sorusuna bağlıdır. Ağırlıklı derece merkeziyeti yalnızca doğrudan bağlantıları yakalarken, Weighted PageRank tüm ağ boyunca yayılan küresel prestiji yakalar. Yerel etki için ağırlıklı dereceyi ve ağ çapında önem için Weighted PageRank'i kullanın.

İlgili yöntemler

Kaynaklar

  1. Xing, W., & Ghorbani, A. (2004). Weighted PageRank algorithm. Proceedings of the Second Annual Conference on Communication Networks and Services Research (CNSR '04), pp. 305–314. IEEE.

    DOI kaynağını aç
    Kopyalandı.
  2. PageRank. Wikipedia.

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