PageRank

Article on other languages:

PageRank je algoritmus pro ohodnocení důležitosti webových stránek, navržený Larry Pagem a Sergeyem Brinem, tvořící základ vyhledávače Google. (Jméno algoritmu je přeložitelné “hodnocení stránky” nebo též “Pageovo ohodnocení”. Podle vyjádření společnosti Google byl algoritmus pojmenován právě po Pageovi.)

Algoritmus využívá strukturu hypertextových odkazů jako vzájemné “doporučování” stránek, ne nepodobné hodnocení vědeckých prací podle počtu citací. Na rozdíl od sledování počtu citací ale dovádí tento princip ještě dál: hodnocení stránky se nepočítá z prostého počtu odkazů, které na ni vedou, ale bere se v úvahu i hodnocení odkazujících stránek.


Chceme-li tedy spočítat PageRank R(a) stránky a, můžeme použít vzorec, který vypadá asi takto:

R(a) = \sum_{u \in B_a } \frac{R(u)}{N_u}

kde Ba je množina všech stran, které odkazují na a, a Nu je počet odkazů, které vedou z u. Každá stránka tak své hodnocení v podstatě předává dál skrze odkazy.

Distribuce PageRanku mezi provázanými stránkami

Rovnice se ještě upravuje normalizujícím faktorem c tak, aby součet všech hodnocení byl konstantní:

R(a) = c \sum_{u \in B_a } \frac{R(u)}{N_u}

Hodnoty PageRanku se dají spočítat pomocí přiřazení libovolných hodnot, a následným iterováním výpočtu, dokud hodnoty nezačnou konvergovat.

Problémem při výpočtu PageRanku jsou uzavřené struktury stránek, u nichž vedou odkazy dovnitř, ale už ne ven.

Například dvě vzájemně propojené strany, s odkazem vedoucím zvenku na jednu z nich, by při výpočtu PageRank akumulovaly, ale nic by nepouštěly ven (protože není kudy). Tím vzniká jakási past, kterou Page a Brin nazývají rank sink.

Stabilní přiřazení PageRanku v uzavřené struktuře stránek

Rank sinky lze vyřešit přidáním zdroje ranku: výchozí hodnoty, kterou má každá stránka sama od sebe. Pak lze upravený PageRank definovat jako zobrazení, které splňuje rovnici

R'(a) = c \left (\sum_{u \in B_a } \frac{R'(u)}{N_u} + E(a) \right )

kde c je pokud možno kladná konstanta a norma R' je rovna jedné. E potom označuje zdroj ranku.

V maticovém zápisu zapíšeme uvedenou rovnici jako R' = c(AR' + E) (A je přitom matice, kde na pozici [a,b] je \frac 1 {N_b}, vede-li odkaz z b do a, v ostatních případech 0).

Protože norma R' je 1, můžeme rovnici přepsat jako R' = c (A + E \times 1) R' (kde 1 je jednotkový vektor). Tudíž R' je vlastní vektor (A + E \times 1).

Výpočet PageRanku

Jak již bylo zmíněno, PageRank lze spočítat postupnou iterací:

  1. Zvolme počáteční vektor hodnocení S (například můžeme použít E)
  2. R0 = s
  3. Cyklus:
    1. Ri + 1 = ARi
    2. d = \lVert R_i \rVert_1 - \lVert R_{i+1} \rVert_1
    3. Ri + 1 = Ri + 1 + dE
    4. \delta = \lVert R_{i+1} - R_i \rVert
  4. Opakujeme cyklus, dokud δ > ε

Faktor d ovlivňuje rychlost konvergence a zachovává celkovou normu výsledku.

Neznámým prvkem ve výpočtu jsou “visící odkazy”: odkazy na stránky, z nichž už nic nevede. V praxi se často jedná o odkazy na stránky, které ještě nejsou v databázi vyhledávače nebo odkazy na stránky, ze kterých už žádný odkaz nevede (typicky např. některé fotogalerie). Problém se může řešit jednoduše tak, že se tyto odkazy při výpočtu PageRanku zanedbají, nebo složitěji tak, že se na takovou stránku přidá virtuální odkaz zpětný.

Přizpůsobení PageRanku

Při výpočtu PageRanku se používá vektor zdroje ranku E. Kromě řešení problému “rank sinks” je to i mocný nástroj k hodnocení stránek z “různých perspektiv” – při použití upraveného vektoru E lze například označit vybranou množinu stránek za důležité pro uživatele, a hodnocení stránek ostatních bude určeno jejich relativním postavením v síti odkazů vůči těmto vybraným stránkám.

Tímto způsobem je teoreticky možné vytvořit vyhledávač přizpůsobený pro konkrétního uživatele – stačí zvolit vektor E, který bude vysoko hodnotit třeba obsah složky jeho složky “oblíbené”. Potom například dotaz “baterie” vrátí elektrotechnikovi stránky o elektrickém článku, zatímco fanouškovi vojenství informace o dělostřelbě.

Vzhledem k výpočetní náročnosti přepočítávání PageRanku pro každého uživatele zvlášť se tento postup ovšem nepoužívá.

Externí odkazy

Citováno z „http://cs.wikipedia.org/wiki/PageRank“

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car
James Bond Guide
This site monitored by SitePinger.net