Zobrazení zdroje stránky PageRank

'''PageRank''' je [[algoritmus]] pro ohodnocení důležitosti [[World Wide Web|webových]] stránek, navržený [[Larry Page]]m a [[Sergey Brin|Sergeyem Brinem]], tvořící základ vyhledávače [[Google (vyhledávač)|Google]]. (Název algoritmu je dvojsmyslný, šlo by ho přeložit jako „stránkové hodnocení“ nebo „Pageovo hodnocení“. Podle vyjádření společnosti [[Google]] byl algoritmus pojmenován právě po Pageovi.<ref>[https://web.archive.org/web/20090424093934/http://www.google.com/press/funfacts.html „Google Press Center: Fun Facts“]. www.google.com. Archivováno z [http://www.google.com/press/funfacts.html původní stránky] dne 2009-04-24.</ref>)

Algoritmus využívá strukturu [[hypertext]]ových odkazů jako vzájemné „doporučování“ stránek, ne nepodobné hodnocení vědeckých prací podle počtu [[citace|citací]]. Na rozdíl od sledování počtu citací však 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, signály ze sociálních sítí apod.

== Princip ==
Chceme-li tedy spočítat PageRank ''R(a)'' stránky ''a'', můžeme použít vzorec ([[Markovův řetězec]])

<math>R(a) = \sum_{u \in B_a } \frac{R(u)}{N_u}</math>

kde <math>B_a</math> je množina všech stránek, které odkazují na ''a'', a <math>N_u</math> je počet odkazů, které vedou z ''u''. Každá stránka tak své hodnocení v podstatě předává dál skrze odkazy.

[[Soubor:Pagerank1.png|thumb|300px|Distribuce PageRanku mezi provázanými stránkami]]

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 [[Konvergence|konvergovat.]] Iterační výpočet je tedy přímo [[Mocninná metoda|mocninnou metodou]] pro výpočet (levého) [[Vlastní číslo|vlastního vektoru]] odpovídajícího dominantnímu vlastnímu číslu [[Stochastická matice|stochastické]] [[matice incidence]] grafu, který reprezentuje odkazy na webu.

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''. 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

<math>R'(a) = c \left(\sum_{u \in B_a } \frac{R'(u)}{N_u}\right) + (1-c)R'(a)</math>

kde <math>c\in[0,1]</math> je kladná konstanta. 

V [[matice|maticovém]] zápisu zapíšeme uvedenou rovnici jako <math>R' = R'(cA + (1-c)E)</math>'', kde A'' je stochastická incidenční matice, kde na pozici (a,u) je <math>1/{N_u}</math>, vede-li odkaz z u do ''a'', v ostatních případech 0, a ''E'' je matice ze samých jedniček.

Vektor PageRanků ''R'' je tedy (levým) vlastním vektorem matice ''A'', vektor ''R<nowiki>'</nowiki>'' matice ''cA+''(1''-c'')''E''. Vlastní vektor je normovaný tak aby <math>\|R\|_1=\|R'\|_1=1</math>.

== Výpočet PageRanku ==
Jak již bylo zmíněno, PageRank lze spočítat postupnou iterací:
# Zvolme počáteční vektor hodnocení ''S'' (například můžeme použít ''E'')
# <math>R_0 = s</math>
# Cyklus:
## <math>R_{i+1} = A R_i</math>
## <math>d = \lVert R_i \rVert_1 - \lVert R_{i+1} \rVert_1</math>
## <math>R_{i+1} = R_{i+1} + d E</math>
## <math>\delta = \lVert R_{i+1} - R_i \rVert</math>
# Opakujeme cyklus, dokud <math>\delta > \varepsilon</math>

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

Trochu problematické jsou ve výpočtu tzv. visící stránky (dangling nodes). V praxi se často jedná o stránky, ze kterých už žádný odkaz nevede (obrázky jpg, gif, ..., často také dokumenty doc, [[Portable Document Format|pdf]], ..., atd). Výše uvedená matice ''A'' je právě z důvodů visících stránek trochu poškozena a není stochastická, ale tzv. substochastická. Tento problém se řeší obdobně jako výše zmíněné rank sinky, které, pro změnu, způsobují [[Rozložitelná matice|rozložitelnost matice]] ''A''. Rozložitelnost i substochasticita negativně ovlivňují proveditelnost výpočtu.

== 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á.

== Odkazy ==

=== Související články ===

* [[Markovův řetězec]]
* [[Stochastická matice]]

=== Reference ===
<references />

=== Externí odkazy ===
* {{Commonscat}}
* M. Hejlová: ''[https://www.fp.tul.cz/~plesinger/students/Hejlova_2015.pdf Google PageRank: Relevance webových stránek a problém vlastních čísel]'', bakalářská práce, TUL, 2015 (detailní popis zavedení PageRanku včetně matematického pozadí)
* [http://www.jakpsatweb.cz/seo/pagerank.html Google PageRank] (vysvětlení na stránkách Dušana Janovského)
* [http://www.lupa.cz/clanky/zahadny-google-toolbar-pagerank/ Toolbarový PageRank] (vysvětlení zeleného měřítka zobrazovaného Google Toolbarem)
* [[Larry Page|Lawrence Page]], [[Sergey Brin]], Rajeev Motwani, Terry Winograd: [http://www.voelspriet2.nl/PageRank.pdf The PageRank Citation Ranking: Bringing Order to the Web] {{Wayback|url=http://www.voelspriet2.nl/PageRank.pdf |date=20050915094717 }}, [[Stanfordova univerzita]], November 1999 (anglicky)
* Chris Ridings, Mike Shishigin: [https://web.archive.org/web/20080912112513/http://dbpubs.stanford.edu:8090/pub/1999-66 PageRank Uncovered], version 3.0, September 2002 (anglicky)

{{Google}}
{{Portály|Internet}}
[[Kategorie:Vyhledávací algoritmy]]
[[Kategorie:Google]]
[[Kategorie:Webometrie]]
[[Kategorie:Optimalizace pro vyhledávače]]