Sayfa Sıralaması - PageRank

Basit bir ağ için matematiksel PageRank'ler yüzde olarak ifade edilir. (Google bir logaritmik ölçek kullanır .) C Sayfasına daha az bağlantı olmasına rağmen, C Sayfasının PageRank'i Sayfa E'den daha yüksektir; C'ye giden tek bağlantı önemli bir sayfadan gelir ve bu nedenle yüksek değerdedir. Rastgele bir sayfadan başlayan web sörfçüleri, şu anda ziyaret ettikleri sayfadan rastgele bir bağlantı seçme olasılığı %82,5 ve tüm web'den rastgele seçilen bir sayfaya atlama olasılığı %17,5 ise, Sayfa E'ye ulaşacaklardır. %8,1 oranında. (Rastgele bir sayfaya atlamanın %17,5 olasılığı, %82,5'lik bir sönümleme faktörüne karşılık gelir .) Sönümleme olmadan, tüm web sörfçüleri sonunda A, B veya C Sayfalarına gelir ve diğer tüm sayfalarda PageRank sıfır olur. Sönümlemenin varlığında, Sayfa A, kendi giden bağlantıları olmamasına rağmen, web'deki tüm sayfalara etkin bir şekilde bağlanır.

PageRank ( PR ) bir olan algoritma kullandığı Google Arama sıralaması için web sayfaları kendi içinde arama motoru sonuçlarında. Hem "web sayfası" teriminden hem de kurucu ortak Larry Page'den almıştır . PageRank, web sitesi sayfalarının önemini ölçmenin bir yoludur. Google'a göre:

PageRank, web sitesinin ne kadar önemli olduğuna dair kabaca bir tahmin belirlemek için bir sayfaya verilen bağlantıların sayısını ve kalitesini sayarak çalışır. Temel varsayım, daha önemli web sitelerinin diğer web sitelerinden daha fazla bağlantı alması muhtemeldir.

Şu anda PageRank, Google tarafından arama sonuçlarını sıralamak için kullanılan tek algoritma değil, şirket tarafından kullanılan ilk algoritmadır ve en çok bilinenidir. 24 Eylül 2019 itibariyle, PageRank ve ilgili tüm patentlerin süresi dolmuştur.

Açıklama

PageRank'in temel ilkesini gösteren karikatür. Her yüzün boyutu, ona işaret eden diğer yüzlerin toplam boyutuyla orantılıdır.

PageRanks bir bağlantı analizi algoritmasıdır ve küme içindeki göreceli önemini "ölçmek" amacıyla, World Wide Web gibi hiper bağlantılı bir belge kümesinin her bir öğesine sayısal bir ağırlık atar . Algoritma ile varlıkların herhangi koleksiyonuna uygulanabilir karşılıklı alıntılar ve referanslar. Herhangi bir E öğesine atadığı sayısal ağırlık, E'nin PageRank'i olarak adlandırılır ve ile gösterilir.

Bir PageRank , cnn.com veya mayoclinic.org gibi otorite merkezleri dikkate alınarak, tüm World Wide Web sayfaları tarafından düğümler ve köprüler olarak kenarlar olarak oluşturulan web grafiğine dayalı bir matematiksel algoritmadan elde edilir . Sıra değeri, belirli bir sayfanın önemini belirtir. Bir sayfaya köprü, destek oyu olarak sayılır. Bir sayfanın PageRank'i özyinelemeli olarak tanımlanır ve ona bağlanan tüm sayfaların (" gelen bağlantılar ") sayısına ve PageRank metriğine bağlıdır . Yüksek PageRank'e sahip birçok sayfa tarafından bağlantı verilen bir sayfanın kendisi de yüksek bir sıralama alır.

Page ve Brin'in orijinal makalesinden bu yana PageRank ile ilgili çok sayıda akademik makale yayınlanmıştır. Pratikte, PageRank kavramı manipülasyona açık olabilir. Yanlış bir şekilde etkilenen PageRank sıralamalarını belirlemek için araştırmalar yapılmıştır. Amaç, yanlış bir şekilde PageRank'ten etkilenmiş belgelerden gelen bağlantıları yok saymanın etkili bir yolunu bulmaktır.

Web sayfaları için diğer bağlantı tabanlı sıralama algoritmaları içermektedir HITS algoritmasında tarafından icat Jon Kleinberg (kullandığı Teoma ve şimdi Ask.com ), IBM AKILLI projesi , TrustRank algoritması ve Hummingbird algoritması.

Tarih

Özdeğer problemi üzerinde çalıştı Gabriel Pinski ve Francis Narin tarafından 1976 yılında öne sürüldü Scientometrics tarafından 1977 yılında, bilimsel dergi sıralamasında Thomas Saaty kavramında yaptığı Analitik Hiyerarşi Süreci bir şekilde Bradley Sevgi ve Steven Sloman tarafından 1995 yılında ağırlıklı alternatif seçenekler ve kavramlar için bilişsel model , merkezilik algoritması.

1996 yılında Robin Li tarafından tasarlanan IDD Bilgi Hizmetleri'nden " RankDex " adlı bir arama motoru , site puanlama ve sayfa sıralama için bir strateji geliştirdi. Li, arama mekanizmasına, bir web sitesinin popülaritesini, ona bağlanan diğer kaç siteye dayalı olarak sıralamayı içeren "bağlantı analizi" olarak atıfta bulundu. RankDex, sayfa sıralama ve site puanlama algoritması ile ilk arama motoru, onun patenti 1999 yılında 1997 yılında açılan ve verilen ile Li RankDex teknolojiyi patentli 1996 yılında başlatılan kurduğu zaman o daha sonra kullanıldı Baidu yılında Çin'de 2000. Google'ın kurucusu Larry Page , PageRank için ABD'deki bazı patentlerinde Li'nin çalışmasına atıfta bulundu.

Larry Page ve Sergey Brin , 1996 yılında Stanford Üniversitesi'nde yeni bir tür arama motoruyla ilgili bir araştırma projesinin parçası olarak PageRank'i geliştirdi . Stanford Bilgisayar Bilimleri Profesörü ve Sergey Danışmanı Héctor García-Molina ile yapılan bir röportaj , sayfa sıralaması algoritmasının geliştirilmesine ilişkin arka plan sağlar. Sergey Brin, web'deki bilgilerin bir hiyerarşide "bağlantı popülerliği"ne göre sıralanabileceği fikrine sahipti: bir sayfa, daha fazla bağlantı olduğu için daha üst sıralarda yer alır. Sistem, her ikisi de Page ve Brin tarafından Google'ın gelişimi için kritik olarak belirtilen Scott Hassan ve Alan Steremberg'in yardımıyla geliştirildi. Rajeev Motwani ve Terry Winograd , Page ve Brin ile birlikte, PageRank'i ve 1998'de yayınlanan Google arama motorunun ilk prototipini açıklayan proje hakkındaki ilk makaleyi yazdı . Kısa bir süre sonra, Page ve Brin , Google Inc.'i kurdu . Google arama motoru. Google arama sonuçlarının sıralamasını belirleyen birçok faktörden sadece biri olsa da, PageRank Google'ın tüm web arama araçları için temel oluşturmaya devam ediyor.

"PageRank" adı, geliştirici Larry Page'in yanı sıra bir web sayfası konseptinde de oynanır . Kelime, Google'ın ticari markasıdır ve PageRank işleminin patenti alınmıştır ( ABD Patenti 6,285,999 ). Ancak, patent Google'a değil Stanford Üniversitesi'ne aittir . Google, Stanford Üniversitesi'nden alınan patent üzerinde münhasır lisans haklarına sahiptir. Üniversite, patentin kullanımı karşılığında 1.8 milyon Google hissesi aldı; hisselerini 2005 yılında 336 milyon dolara sattı.

PageRank etkilendi atıf analizi erken tarafından geliştirilen, Eugene Garfield Pennsylvania Üniversitesi'nde 1950'lerde ve tarafından Hiper Arama tarafından geliştirilen, Massimo Marchiori de Padua Üniversitesi . PageRank'in tanıtıldığı aynı yıl (1998), Jon Kleinberg HITS üzerine çalışmasını yayınladı . Google'ın kurucuları, orijinal makalelerinde Garfield, Marchiori ve Kleinberg'den alıntı yapıyor.

algoritma

PageRank algoritması , bağlantılara rastgele tıklayan bir kişinin herhangi bir belirli sayfaya ulaşma olasılığını temsil etmek için kullanılan bir olasılık dağılımı verir. PageRank, herhangi bir boyuttaki belge koleksiyonları için hesaplanabilir. Çeşitli araştırma makalelerinde, hesaplama sürecinin başlangıcında, dağılımın koleksiyondaki tüm belgeler arasında eşit olarak bölündüğü varsayılmaktadır. PageRank hesaplamaları, teorik gerçek değeri daha yakından yansıtmak için yaklaşık PageRank değerlerini ayarlamak için koleksiyonda "yinelemeler" adı verilen birkaç geçiş gerektirir.

Olasılık, 0 ile 1 arasında sayısal bir değer olarak ifade edilir. 0,5 olasılık, genellikle bir şeyin gerçekleşmesi için "%50 şans" olarak ifade edilir. Bu nedenle, PageRank'i 0,5 olan bir belge, rastgele bir bağlantıya tıklayan bir kişinin söz konusu belgeye yönlendirilme olasılığının %50 olduğu anlamına gelir.

Basitleştirilmiş algoritma

Dört web sayfasından oluşan küçük bir evren varsayın: A , B , C ve D . Bir sayfadan kendisine verilen bağlantılar yok sayılır. Bir sayfadan diğerine giden birden çok bağlantı, tek bir bağlantı olarak kabul edilir. PageRank, tüm sayfalar için aynı değere başlatılır. PageRank'in orijinal biçiminde, tüm sayfalardaki PageRank'in toplamı, o sırada web'deki toplam sayfa sayısıydı, bu nedenle bu örnekteki her sayfanın başlangıç ​​değeri 1 olacaktır. Ancak, PageRank'in sonraki sürümleri ve Bu bölümün geri kalanında 0 ile 1 arasında bir olasılık dağılımı olduğunu varsayalım . Dolayısıyla bu örnekteki her sayfanın başlangıç ​​değeri 0.25'tir.

Bir sonraki iterasyonda belirli bir sayfadan kendi giden bağlantılarının hedeflerine aktarılan PageRank, tüm giden bağlantılar arasında eşit olarak bölünür.

Sisteminde sadece bağlantılar sayfalarından olsaydı B , C ve D için , A , her bir bağlantı 0.25 PageRank'e transfer olur A 0.75 toplam sonraki iterasyon üzerine.

Bunun yerine B sayfasının C ve A sayfalarına bir bağlantısı olduğunu , C sayfasının A sayfasına bir bağlantısı olduğunu ve D sayfasının üç sayfanın tümüne bağlantılara sahip olduğunu varsayalım . Böylece, ilk yinelemede, B sayfası mevcut değerinin yarısını veya 0.125'i sayfa A'ya ve diğer yarısını veya 0.125'i sayfa C'ye aktarır . C Sayfası , mevcut 0.25 değerinin tamamını, bağlantı verdiği tek sayfa olan A'ya aktarır . Yana Ge üç Giden bağlantıları vardı, bir mevcut değerinin üçte veya 0,083, aktaracak A . Bu yinelemenin sonunda A sayfasının PageRank değeri yaklaşık 0,458 olacaktır.

Başka bir deyişle, bir giden bağlantı tarafından verilen PageRank, belgenin kendi PageRank puanının giden bağlantıların sayısına bölünmesiyle elde edilen L( ) değerine eşittir .

Genel durumda, herhangi bir sayfa u için PageRank değeri şu şekilde ifade edilebilir:

,

yani, bir sayfa için PageRank değeri u her sayfa PageRank değerlerine bağlıdır v grubu içerdiği B u (sayfasına bağlayan tüm sayfaları içeren grubu u sayısı ile bölünür), L ( hacim sayfa bağlantıları) v .

sönümleme faktörü

PageRank teorisi, bağlantılara rastgele tıklayan hayali bir sörfçünün sonunda tıklamayı bırakacağını savunur. Herhangi bir adımda kişinin devam etme olasılığı bir sönümleme faktörüdür d . Çeşitli çalışmalar farklı sönümleme faktörlerini test etmiştir, ancak genellikle sönüm faktörünün 0.85 civarında ayarlanacağı varsayılmaktadır.

Sönüm faktörü 1'den çıkarılır (ve algoritmanın bazı varyasyonlarında sonuç, koleksiyondaki belge sayısına ( N ) bölünür ) ve bu terim daha sonra sönüm faktörünün çarpımına ve toplamına eklenir. gelen PageRank puanları. Yani,

Dolayısıyla herhangi bir sayfanın PageRank'i, büyük ölçüde diğer sayfaların PageRank'lerinden türetilir. Sönümleme faktörü, türetilen değeri aşağı doğru ayarlar. Ancak orijinal makale, bazı kafa karışıklığına yol açan aşağıdaki formülü verdi:

Aralarındaki fark, birinci formüldeki PageRank değerlerinin bire eşit olması, ikinci formülde ise her PageRank değerinin N ile çarpılması ve toplamın N olmasıdır . Page ve Brin'in makalesinde yer alan "tüm PageRank'lerin toplamı birdir" ifadesi ve diğer Google çalışanlarının iddiaları, yukarıdaki formülün ilk varyantını desteklemektedir.

Page ve Brin, en popüler makaleleri olan "The Anatomy of a Large-Scale Hypertextual Web Search Engine" adlı makalelerinde iki formülü karıştırdılar ve burada yanlışlıkla ikinci formülün web sayfaları üzerinde bir olasılık dağılımı oluşturduğunu iddia ettiler.

Google, Web'i her taradığında PageRank puanlarını yeniden hesaplar ve dizinini yeniden oluşturur. Google, koleksiyonundaki doküman sayısını artırdıkça, tüm dokümanlar için PageRank'in başlangıçtaki tahmini azalır.

Formül, birkaç tıklamadan sonra hedef sitesine ulaşan ve ardından rastgele bir sayfaya geçen rastgele bir sörfçünün modelini kullanır . Bir sayfanın PageRank değeri, rastgele sörfçünün bir bağlantıya tıklayarak o sayfaya gelme şansını yansıtır. Durumların sayfalar olduğu ve geçişlerin sayfalar arasındaki bağlantılar olduğu bir Markov zinciri olarak anlaşılabilir - hepsi eşit derecede olasıdır.

Bir sayfanın diğer sayfalara bağlantısı yoksa, bir havuz olur ve bu nedenle rastgele gezinme sürecini sonlandırır. Rastgele sörfçü bir havuz sayfasına ulaşırsa, rastgele başka bir URL seçer ve yeniden gezinmeye devam eder.

PageRank hesaplanırken, giden bağlantısı olmayan sayfaların, koleksiyondaki diğer tüm sayfalara bağlantı verdiği varsayılır. Bu nedenle PageRank puanları diğer tüm sayfalar arasında eşit olarak bölünür. Diğer bir deyişle, batmayan sayfalarla adil olmak için, bu rastgele geçişler Web'deki tüm düğümlere eklenir. Bu artık olasılık, d , genellikle ortalama bir sörfçünün tarayıcısının yer imi özelliğini kullanma sıklığından tahmin edilen 0.85'e ayarlanır. Yani, denklem aşağıdaki gibidir:

nerede göz altında sayfalarıdır, bağlantı Söz konusu sayfa kümesidir , sayfadaki giden bağlantıların sayısının ve toplam sayfa sayısıdır.

PageRank değerleri , değiştirilmiş komşuluk matrisinin baskın sağ özvektörünün girişleridir, böylece her sütun bir taneye kadar ekler. Bu, PageRank'i özellikle zarif bir metrik yapar: özvektör

burada R denklemin çözümüdür

burada bitişiklik işlevi , j sayfasından i sayfasına giden bağlantıların sayısı ile j sayfasındaki toplam giden bağlantıların sayısı arasındaki orandır. Sayfa eğer bitişiklik fonksiyonu 0 bağlantı vermediğinden her biri için, ve bu tür normalize j

,

yani, her sütunun öğelerinin toplamı 1'dir, bu nedenle matris stokastik bir matristir (daha fazla ayrıntı için aşağıdaki hesaplama bölümüne bakın). Dolayısıyla bu, ağ analizinde yaygın olarak kullanılan özvektör merkezilik ölçüsünün bir çeşididir .

Yukarıdaki değiştirilmiş komşuluk matrisinin büyük öz alanı nedeniyle, PageRank özvektörünün değerleri, yalnızca birkaç yineleme içinde yüksek bir doğruluk derecesi içinde yaklaşık olarak tahmin edilebilir.

Google'ın kurucuları, orijinal makalelerinde, 322 milyon bağlantıdan (iç ve dış kenarlar) oluşan bir ağ için PageRank algoritmasının 52 yinelemede tolere edilebilir bir sınırda yakınsadığını bildirdi. Yukarıdaki boyutun yarısı olan bir ağdaki yakınsama yaklaşık 45 yineleme aldı. Bu veriler aracılığıyla, algoritmanın çok iyi ölçeklenebileceği ve aşırı büyük ağlar için ölçeklendirme faktörünün kabaca doğrusal olacağı sonucuna vardılar , burada n ağın boyutudur.

Markov teorisinin bir sonucu olarak , bir sayfanın PageRank'inin çok sayıda tıklamadan sonra o sayfaya ulaşma olasılığı olduğu gösterilebilir. Bu , sayfadan kendisine geri dönmek için gereken tıklama (veya rastgele atlama) sayısının beklentisinin nerede olduğu ile aynı olur .

PageRank'in ana dezavantajlarından biri, eski sayfaları tercih etmesidir. Yeni bir sayfa, hatta çok iyi bir sayfa, mevcut bir sitenin parçası olmadığı sürece (bir site, Wikipedia gibi yoğun bir şekilde bağlantılı sayfalardan oluşan bir site) çok fazla bağlantıya sahip olmayacaktır .

PageRank hesaplamasını hızlandırmak için çeşitli stratejiler önerilmiştir.

Arama sonuçları sıralamasını iyileştirmek ve reklam bağlantılarından para kazanmak için yapılan ortak çabalarda PageRank'i manipüle etmek için çeşitli stratejiler kullanılmıştır. Bu stratejiler, Web topluluğu tarafından hangi belgelere gerçekten çok değer verildiğini belirlemeyi amaçlayan PageRank kavramının güvenilirliğini ciddi şekilde etkilemiştir.

Google, ücretli metin bağlantıları satan siteleri aktif olarak cezalandırmaya başladığı Aralık 2007'den bu yana, bağlantı çiftlikleri ve PageRank'i yapay olarak şişirmek için tasarlanmış diğer planlarla mücadele ediyor. Google'ın bağlantı çiftliklerini ve diğer PageRank manipülasyon araçlarını nasıl tanımladığı, Google'ın ticari sırları arasındadır .

Hesaplama

PageRank, yinelemeli veya cebirsel olarak hesaplanabilir. Yinelemeli yöntem, güç yineleme yöntemi veya güç yöntemi olarak görülebilir . Gerçekleştirilen temel matematiksel işlemler aynıdır.

yinelemeli

'de , bir başlangıç ​​olasılık dağılımı varsayılır, genellikle

.

burada N toplam sayfa sayısıdır ve 0 zamanında sayfa i'dir.

Her zaman adımında, yukarıda ayrıntılı olarak açıklanan hesaplama,

burada d sönümleme faktörüdür,

veya matris notasyonunda

,

 

 

 

 

( 1 )

nerede ve sadece bir tane içeren uzunluk sütun vektörüdür .

Matris şu şekilde tanımlanır:

yani,

,

burada grafiğin komşuluk matrisini belirtir ve köşegende dereceleri olan köşegen matristir.

Olasılık hesaplaması her sayfa için bir zaman noktasında yapılır, ardından bir sonraki zaman noktası için tekrarlanır. Hesaplama, bazı küçük

,

yani yakınsama varsayıldığında.

Güç yöntemi

Matris ise bir geçiş olasılığı, örneğin, kolon-stokastik ve bir olasılık dağılım (diğer bir deyişle, , burada daha sonra, denklem (tüm olanların matristir) 2 ) eşdeğerdir

.

 

 

 

 

( 3 )

Dolayısıyla PageRank , 'nin ana özvektörüdür . Bunu hesaplamanın hızlı ve kolay bir yolu, güç yöntemini kullanmaktır : keyfi bir vektörle başlayarak , operatör art arda uygulanır, yani,

,

a kadar

.

Denklemde ( 3 ) parantez içinde sağ taraftaki matrisin şu şekilde yorumlanabileceğine dikkat edin:

,

nerede bir başlangıç ​​olasılık dağılımıdır. n mevcut durum

.

Son olarak, yalnızca sıfır değerine sahip sütunlar varsa , bunlar ilk olasılık vektörü ile değiştirilmelidir . Diğer bir deyişle,

,

matrisin tanımlandığı yer

,

ile birlikte

Bu durumda, kullanılan yukarıdaki iki hesaplama, yalnızca sonuçları normalleştirilmişse aynı PageRank'i verir:

.

uygulama

Scala / Apache Kıvılcımı

Tipik bir örnek, Sayfa Sıralarını yinelemeli olarak hesaplamak için Scala'nın Apache Spark RDD'leri ile işlevsel programlamasını kullanmaktır.

object SparkPageRank {
  def main(args: Array[String]) {
    val spark = SparkSession
      .builder
      .appName("SparkPageRank")
      .getOrCreate()

    val iters = if (args.length > 1) args(1).toInt else 10
    val lines = spark.read.textFile(args(0)).rdd
    val links = lines.map{ s =>
      val parts = s.split("\\s+")
      (parts(0), parts(1))
    }.distinct().groupByKey().cache()
    
    var ranks = links.mapValues(v => 1.0)

    for (i <- 1 to iters) {
      val contribs = links.join(ranks).values.flatMap{ case (urls, rank) =>
        val size = urls.size
        urls.map(url => (url, rank / size))
      }
      ranks = contribs.reduceByKey(_ + _).mapValues(0.15 + 0.85 * _)
    }

    val output = ranks.collect()
    output.foreach(tup => println(tup._1 + " has rank: " + tup._2 + "."))

    spark.stop()
  }
}

MATLAB / Oktav

% Parameter M adjacency matrix where M_i,j represents the link from 'j' to 'i', such that for all 'j'
%     sum(i, M_i,j) = 1
% Parameter d damping factor
% Parameter v_quadratic_error quadratic error for v
% Return v, a vector of ranks such that v_i is the i-th rank from [0, 1]

function [v] = rank2(M, d, v_quadratic_error)

N = size(M, 2); % N is equal to either dimension of M and the number of documents
v = rand(N, 1);
v = v ./ norm(v, 1);   % This is now L1, not L2
last_v = ones(N, 1) * inf;
M_hat = (d .* M) + (((1 - d) / N) .* ones(N, N));

while (norm(v - last_v, 2) > v_quadratic_error)
	last_v = v;
	v = M_hat * v;
        % removed the L2 norm of the iterated PR
end

end %function

Yukarıda tanımlanan sıralama işlevini çağıran kod örneği:

M = [0 0 0 0 1 ; 0.5 0 0 0 0 ; 0.5 0 0 0 0 ; 0 1 0.5 0 0 ; 0 0 0.5 1 0];
rank2(M, 0.80, 0.001)

piton

"""PageRank algorithm with explicit number of iterations.

Returns
-------
ranking of nodes (pages) in the adjacency matrix

"""

import numpy as np

def pagerank(M, num_iterations: int = 100, d: float = 0.85):
    """PageRank: The trillion dollar algorithm.

    Parameters
    ----------
    M : numpy array
        adjacency matrix where M_i,j represents the link from 'j' to 'i', such that for all 'j'
        sum(i, M_i,j) = 1
    num_iterations : int, optional
        number of iterations, by default 100
    d : float, optional
        damping factor, by default 0.85

    Returns
    -------
    numpy array
        a vector of ranks such that v_i is the i-th rank from [0, 1],
        v sums to 1

    """
    N = M.shape[1]
    v = np.random.rand(N, 1)
    v = v / np.linalg.norm(v, 1)
    M_hat = (d * M + (1 - d) / N)
    for i in range(num_iterations):
        v = M_hat @ v
    return v

M = np.array([[0, 0, 0, 0, 1],
              [0.5, 0, 0, 0, 0],
              [0.5, 0, 0, 0, 0],
              [0, 1, 0.5, 0, 0],
              [0, 0, 0.5, 1, 0]])
v = pagerank(M, 100, 0.85)

Bu örnek, yakınsamak için ≈13 yineleme gerektirir.

Varyasyonlar

Yönlendirilmemiş bir grafiğin PageRank'i

Yönlendirilmemiş bir grafiğin PageRank'i, grafiğin derece dağılımına istatistiksel olarak yakındır , ancak bunlar genellikle aynı değildir: If , yukarıda tanımlanan PageRank vektörüdür ve derece dağılım vektörüdür

burada köşe derecesini gösterir ve , daha sonra, grafiğin kenar dizi , şunları gösterir:

yani, yönsüz bir grafiğin PageRank'i, ancak ve ancak grafik düzenliyse, yani her köşe aynı dereceye sahipse derece dağılım vektörüne eşittir.

İki tür nesneleri sıralamak için PageRank ve özvektör merkeziliğinin genelleştirilmesi

Daugulis, etkileşim halindeki iki nesne grubunu sıralama durumu için PageRank'in bir genelleştirmesini tanımladı. Uygulamalarda, nesne çiftleri üzerinde ağırlıklı bir ilişkinin tanımlandığı iki tür nesneye sahip sistemleri modellemek gerekli olabilir. Bu, ikili grafiklerin dikkate alınmasına yol açar . Bu tür grafikler için, köşe bölüm kümelerine karşılık gelen iki ilişkili pozitif veya negatif olmayan indirgenemez matris tanımlanabilir. Her iki gruptaki nesnelerin sıralaması, bu matrislerin maksimum pozitif öz değerlerine karşılık gelen özvektörler olarak hesaplanabilir. Normlu özvektörler mevcuttur ve Perron veya Perron-Frobenius teoremi tarafından benzersizdir. Örnek: tüketiciler ve ürünler. İlişki ağırlığı, ürün tüketim oranıdır.

PageRank hesaplaması için dağıtılmış algoritma

Sarma et al. bir ağdaki düğümlerin PageRank'ini hesaplamak için iki rastgele yürüyüş tabanlı dağıtılmış algoritmayı tanımlar . Bir algoritma , herhangi bir grafikte (yönlü veya yönsüz) yüksek olasılıkla tur alır ; burada n, ağ boyutudur ve PageRank hesaplamasında kullanılan sıfırlama olasılığıdır ( , sönümleme faktörü olarak adlandırılır). Ayrıca yönsüz grafiklerde tur alan daha hızlı bir algoritma sunarlar . Her iki algoritmada da, her düğüm, ağ boyutu olan n cinsinden polilogaritmik olan bir dizi biti işler ve her turda gönderir.

Google Araç Çubuğu

Google Araç Çubuğu uzun bir bütün 0 (en az popüler) arasındaki sayı ve 10 (en popüler) gibi ziyaret edilen sayfanın PageRank görüntülenen bir PageRank özelliğini vardı. Google, yalnızca bir web sitesinin değerinin kaba bir göstergesi olarak kabul edilecek olan Araç Çubuğu PageRank değerini belirlemek için belirli bir yöntemi açıklamamıştı. "Araç Çubuğu Pagerank", Google Web Yöneticisi Araçları arayüzü aracılığıyla doğrulanmış site yöneticileri için mevcuttu. Ancak, 15 Ekim 2009'da bir Google çalışanı, şirketin Web Yöneticisi Araçları bölümünden PageRank'i kaldırdığını doğruladı ve "İnsanlara uzun zamandır PageRank'e bu kadar odaklanmamaları gerektiğini söylüyorduk. sahipleri , izlemeleri gereken en önemli metrik olduğunu düşünüyor gibi görünüyor , ki bu kesinlikle doğru değil."

"Araç Çubuğu Pagerank" çok seyrek olarak güncellendi. En son Kasım 2013'te güncellendi. Ekim 2014'te Matt Cutts, başka bir görünür pagerank güncellemesinin gelmeyeceğini duyurdu. Mart 2016'da Google, bu özelliği artık desteklemeyeceğini ve temel alınan API'nin yakında çalışmayı durduracağını duyurdu. 15 Nisan 2016'da Google, Google Araç Çubuğunda PageRank Verilerinin görüntülenmesini resmi olarak kapattı. Google, içeriğin arama sonuçlarında nasıl sıralanacağını belirlerken PageRank puanını kullanmaya devam edecek.

SERP sıralaması

Arama motoru sonuçları sayfası (SERP) bir anahtar kelime sorgusuna yanıt olarak bir arama motoru tarafından döndürülen gerçek bir sonuçtur. SERP, ilişkili metin parçacıklarına sahip web sayfalarına bağlantıların bir listesinden oluşur. Bir web sayfasının SERP sıralaması, ilgili bağlantının SERP'deki yerleşimini ifade eder, burada daha yüksek yerleşim, daha yüksek SERP sıralaması anlamına gelir. Bir web sayfasının SERP sıralaması, yalnızca PageRank'inin değil, aynı zamanda nispeten büyük ve sürekli olarak ayarlanan bir dizi faktörün (200'ün üzerinde) bir işlevidir. Arama motoru optimizasyonu (SEO), bir web sitesi veya bir dizi web sayfası için SERP sıralamasını etkilemeyi amaçlar.

Bir web sayfasının bir anahtar kelime için Google SERP'lerinde konumlandırılması, otorite ve popülerlik olarak da bilinen alaka düzeyine ve itibara bağlıdır. PageRank, Google'ın bir web sayfasının itibarına ilişkin değerlendirmesinin göstergesidir: Anahtar kelimeye özgü değildir. Google, bir anahtar kelime için rekabet eden bir web sayfasının genel yetkisini belirlemek için web sayfası ve web sitesi yetkisinin bir kombinasyonunu kullanır. Bir web sitesinin Ana Sayfasının PageRank'i, Google'ın web sitesi yetkisi için sunduğu en iyi göstergedir.

Google Rehber'in ana organik SERP'ye dahil edilmesinden sonra, PageRank'e ek olarak çok sayıda başka faktör, bir işletmenin Yerel İşletme Sonuçlarında sıralamasını etkiler. Google, Soru-Cevap #Mart 2016'da PageRank'in kullanımdan kaldırılmasının nedenlerini ayrıntılı olarak açıkladığında, Bağlantıları ve İçeriği En İyi Sıralama Faktörleri olarak açıkladı. RankBrain, Ekim 2015'te daha önce 3. Sıralama Faktörü olarak ilan edilmişti, bu nedenle İlk 3 Faktör Google tarafından resmi olarak onaylandı.

Google dizini PageRank

Google Dizin PageRank 8 ünite ölçümü yapıldı. Yeşil çubuğun üzerine gelindiğinde sayısal bir PageRank değeri gösteren Google Araç Çubuğu'nun aksine, Google Dizini yalnızca çubuğu görüntüledi, sayısal değerleri asla göstermedi. Google Dizini 20 Temmuz 2011'de kapatıldı.

Yanlış veya sahte PageRank

Geçmişte, Araç Çubuğunda gösterilen PageRank kolayca manipüle edilirdi. HTTP 302 yanıtı veya "Yenile" meta etiketi aracılığıyla bir sayfadan diğerine yönlendirme , kaynak sayfanın hedef sayfanın PageRank değerini almasına neden oldu. Bu nedenle, PR 0'a sahip yeni bir sayfa ve hiçbir gelen bağlantı, Google ana sayfasına yönlendirilerek PR 10'u alabilirdi. Bu kimlik sahtekarlığı tekniği bilinen bir güvenlik açığıydı. Kimlik sahtekarlığı genellikle bir kaynak URL için bir Google araması yapılarak algılanabilir; sonuçlarda tamamen farklı bir sitenin URL'si görüntüleniyorsa, ikinci URL bir yeniden yönlendirmenin hedefini temsil edebilir.

PageRank'i manipüle etme

İçin arama motoru optimizasyonu amacıyla, bazı şirketler yöneticileri yüksek PageRank bağlantıları satmaya sunuyoruz. Daha yüksek PR sayfalarından gelen bağlantıların daha değerli olduğuna inanıldığından, daha pahalı olma eğilimindedirler. Trafik çekmek ve bir web yöneticisinin bağlantı popülerliğini artırmak için kaliteli ve ilgili sitelerin içerik sayfalarında bağlantı reklamları satın almak etkili ve uygulanabilir bir pazarlama stratejisi olabilir. Ancak Google, web yöneticilerini, PageRank ve itibar kazandırmak amacıyla bağlantı satarlarsa veya sattıkları tespit edilirse, bağlantılarının devalüe edileceği (diğer sayfaların PageRank'lerinin hesaplanmasında dikkate alınmaz) konusunda kamuya açık bir şekilde uyarmıştır. Satın alma ve satma uygulaması, Webmaster topluluğu arasında yoğun bir şekilde tartışılmaktadır. Google, web yöneticilerine sponsorlu bağlantılarda nofollow HTML öznitelik değerini kullanmalarını tavsiye eder . Matt Cutts'a göre Google, sistemi oyuna getirmeye çalışan ve böylece Google arama sonuçlarının kalitesini ve alaka düzeyini düşüren web yöneticileri hakkında endişeli . PageRank, SEO amaçları için daha az önemli hale gelse de, daha popüler web sitelerinden gelen geri bağlantıların varlığı, bir web sayfasını arama sıralamasında daha yukarılara çekmeye devam ediyor.

Yönetmen Sörfçü Modeli

Sayfaların içeriğine ve sörfçünün aradığı sorgu terimlerine bağlı olarak olasılıksal olarak sayfadan sayfaya atlayan daha akıllı bir sörfçü. Bu model, adından da anlaşılacağı gibi aynı zamanda bir sorgu işlevi olan bir sayfanın sorguya bağlı PageRank puanına dayanmaktadır. Çok terimli bir sorgu verildiğinde , sörfçü bazı olasılık dağılımına göre a seçer ve çok sayıda adım için davranışını yönlendirmek için bu terimi kullanır. Daha sonra davranışını belirlemek için dağılıma göre başka bir terim seçer ve bu böyle devam eder. Ziyaret edilen web sayfaları üzerinden elde edilen dağılım QD-PageRank'tir.

Sosyal bileşenler

Katja Mayer, PageRank'i farklı bakış açılarını ve düşünceleri tek bir yerde birleştirdiği için bir sosyal ağ olarak görüyor. İnsanlar bilgi almak için PageRank'e gidiyor ve konuyla ilgili fikirleri olan diğer yazarların alıntılarıyla dolup taşıyor . Bu, düşünmeyi teşvik etmek için her şeyin tartışılabileceği ve toplanabileceği bir sosyal yön yaratır. PageRank ile onu kullananlar arasında, modern toplumdaki değişimlere sürekli uyum sağlayan ve değişen bir sosyal ilişki vardır. PageRank ile birey arasındaki ilişkiyi sosyometri aracılığıyla görüntülemek , ortaya çıkan bağlantıya derinlemesine bir bakış sağlar.

Matteo Pasquinelli, PageRank'in sosyal bir bileşeni olduğu inancının temelinin, dikkat ekonomisi fikrinde yattığını düşünüyor . Dikkat ekonomisi ile, daha fazla insan dikkatini çeken ürünlere değer verilir ve PageRank'in en üstünde yer alan sonuçlar, sonraki sayfalara göre daha fazla odaklanılır. Daha yüksek PageRank'e sahip sonuçlar bu nedenle insan bilincine daha büyük ölçüde girecektir. Bu fikirler karar vermeyi etkileyebilir ve izleyicinin eylemlerinin PageRank ile doğrudan bir ilişkisi vardır. Konumları siteye bağlı dikkat ekonomisini arttırdığından, bir kullanıcının dikkatini çekme potansiyeli daha yüksektir. Bu konumla daha fazla trafik alabilirler ve çevrimiçi pazarlarında daha fazla satın alma olur. Bu sitelerin PageRank'i, onlara güvenilmelerini sağlar ve bu güveni artan işlere dönüştürebilirler.

Diğer kullanımlar

PageRank'in matematiği tamamen geneldir ve herhangi bir alandaki herhangi bir grafik veya ağ için geçerlidir. Bu nedenle, PageRank artık bibliyometri, sosyal ve bilgi ağı analizinde ve bağlantı tahmini ve tavsiyesi için düzenli olarak kullanılmaktadır. Biyoloji, kimya, sinirbilim ve fiziğin yanı sıra yol ağlarının sistem analizi için bile kullanılıyor.

Bilimsel araştırma ve akademi

Pagerank son zamanlarda araştırmacıların bilimsel etkisini ölçmek için kullanıldı. Altta yatan alıntı ve işbirliği ağları, bireysel yazarlara yayılan bireysel yayınlar için bir sıralama sistemi oluşturmak için pagerank algoritması ile birlikte kullanılır. Pagerank-index (Pi) olarak bilinen yeni indeksin, h-index tarafından sergilenen birçok dezavantaj bağlamında h-index'e kıyasla daha adil olduğu gösterilmiştir.

Biyolojideki protein ağlarının analizi için PageRank de faydalı bir araçtır.

Herhangi bir ekosistemde, çevrenin sürekli sağlığı için gerekli olan türleri belirlemek için değiştirilmiş bir PageRank sürümü kullanılabilir.

PageRank'in benzer bir yeni kullanımı, akademik doktora programlarını mezunlarını fakülte pozisyonlarına yerleştirme kayıtlarına göre sıralamaktır. PageRank terimleriyle, akademik bölümler, fakültelerini birbirlerinden (ve kendilerinden) işe alarak birbirleriyle bağlantı kurar.

PageRank bir versiyonu yakın zamanda geleneksel için yedek olarak öne sürülmüştür Bilimsel Bilgi Enstitüsü (ISI) etki faktörü ve uygulanan Eigenfactor yanı sıra at SCImago . Bir dergiye yapılan toplam atıfları saymak yerine, her atıfın "önemi" PageRank tarzında belirlenir.

In nörobilim , bir PageRank nöron bir sinir ağına göreceli ateşleme hızı ile bağıntılı olduğu tespit edilmiştir.

internet kullanımı

Kişiselleştirilmiş PageRank, Twitter tarafından kullanıcılara takip etmek isteyebilecekleri diğer hesapları sunmak için kullanılır.

Swiftype'ın site arama ürünü, her bir web sitesinin önem sinyallerine bakarak ve ana sayfadaki bağlantı sayısı gibi faktörlere dayalı olarak içeriğe öncelik vererek "bireysel web sitelerine özel bir Sayfa Sıralaması " oluşturur.

Bir Web tarayıcısı , bir web taraması sırasında hangi URL'nin ziyaret edileceğini belirlemek için kullandığı bir dizi önemli ölçütten biri olarak PageRank'i kullanabilir. Google'ın oluşturulmasında kullanılan ilk çalışma kağıtlarından biri, Google'ın bir siteyi ne kadar derinden ve ne kadar tarayacağını belirlemek için bir dizi farklı önem metriğinin kullanımını tartışan URL sıralamasıyla verimli taramadır . PageRank, bir URL için gelen ve giden bağlantıların sayısı ve bir sitedeki kök dizinden URL'ye olan uzaklık gibi listelenmiş başka ölçüler olsa da, bu önem ölçütlerinden biri olarak sunulur.

PageRank ayrıca Blogosphere gibi bir topluluğun Web'in tamamı üzerindeki görünür etkisini ölçmek için bir metodoloji olarak da kullanılabilir . Bu yaklaşım, bu nedenle, Ölçeksiz paradigmasının yansıması olarak dikkat dağılımını ölçmek için PageRank'i kullanır .

Diğer uygulamalar

2005 yılında Pakistan'da bir pilot çalışmada, Structural Deep Democracy, SD2 , Contact Youth adlı sürdürülebilir bir tarım grubunda liderlik seçimi için kullanıldı. SD2, seçmen başına en az iki başlangıç ​​vekilini zorunlu kılmanın ek kısıtlamalarıyla birlikte geçişli vekil oyların işlenmesi için PageRank'i kullanır ve tüm seçmenler vekil adaylardır. Uzman vekiller ve belirli sorunlar için doğrudan oylar eklemek gibi daha karmaşık değişkenler SD2'nin üzerine inşa edilebilir, ancak temel şemsiye sistem olarak SD2, genel vekillerin her zaman kullanılmasını zorunlu kılar.

Sporda PageRank algoritması aşağıdakilerin performansını sıralamak için kullanılmıştır: ABD'deki Ulusal Futbol Ligi'ndeki (NFL) takımlar; bireysel futbolcular; ve Elmas Ligi'ndeki sporcular.

PageRank, bireysel alanlara veya sokaklara kaç kişinin (yaya veya araç) geldiğini tahmin etmek için boşlukları veya sokakları sıralamak için kullanılmıştır. Gelen sözcük anlam bunu gerçekleştirmek için kullanılmış olan kelime Anlam belirsizliği giderme , semantik benzerlik otomatik seviye de ve WordNet Synsets böyle olumlu veya olumsuz olarak belirli bir anlam özelliği, sahip ne kadar güçlü göre yöntem.

takip etme

2005'in başlarında Google , HTML bağlantısının ve bağlantı öğelerinin rel özelliği için yeni bir değer olan " nofollow " uyguladı , böylece web sitesi geliştiricileri ve blog yazarları , Google'ın PageRank amaçları için dikkate almayacağı bağlantılar oluşturabilirler; PageRank sisteminde artık bir "oy" oluşturur. Nofollow ilişkisi, spam dizinlemeyle mücadeleye yardımcı olmak amacıyla eklendi .

Örnek olarak, insanlar daha önce PageRank'lerini yapay olarak şişirmek için web sitelerine bağlantılar içeren birçok mesaj panosu gönderisi oluşturabilirdi. nofollow değeriyle, mesaj panosu yöneticileri, gönderilerdeki tüm köprülere otomatik olarak "rel='nofollow'" eklemek için kodlarını değiştirebilir, böylece PageRank'in bu belirli gönderilerden etkilenmesini önleyebilir. Ancak bu kaçınma yöntemi, meşru yorumların bağlantı değerini azaltmak gibi çeşitli dezavantajlara da sahiptir. (Bakınız: Bloglarda spam#nofollow )

Bir web sitesindeki sayfalar arasındaki PageRank akışını manuel olarak kontrol etme çabasıyla, birçok web yöneticisi, PageRank'i bu sayfalara yönlendirmek için bir web sitesinin belirli dahili bağlantılarına stratejik olarak nofollow niteliğini yerleştirme eylemi olan PageRank Sculpting olarak bilinen şeyi uygular. web yöneticisinin en önemli gördüğü sayfalar. Bu taktik nofollow özelliğinin başlangıcından beri kullanılmaktadır, ancak Google'ın PageRank transferini nofollow ile engellemenin o PageRank'i diğer bağlantılara yönlendirmediğini duyurmasından bu yana artık etkili olmayabilir.

Ayrıca bakınız

Referanslar

alıntılar

Kaynaklar

İlgili patentler

Dış bağlantılar

(Google, logaritmik bir ölçek kullanır.)