PageRank a jeho rozšíření

Vysvětlovat pojem Google PageRank by bylo nošením dříví do lesa – byl už i v českých podmínkách lépe či hůře popsán několikrát. Navíc vzorec, ze kterého vychází, je běžná vysokoškolská matematika a lze jej najít v mnoha učebnicích, dokonce i velmi starých. Na tomto místě PageRank jen opíšu příměrem, který nebývá příliš často uváděn:

Představme si uživatele, který zcela náhodně kliká na odkazy, a tímto způsobem se donekonečna pohybuje po webu. Jen občas (řekněme v 15 procentech případů) místo kliknutí přeskočí na zcela náhodný dokument. PageRank stránky je pravděpodobnost, že se tento náhodný uživatel bude v nějaký okamžik na této stránce vyskytovat.

Vidíte, je to jednoduché. Právě jednoduchost myšlenky a velmi snadný výpočet PageRanku jej předurčily k použití ve vyhledavači – PageRank je možné i pro miliardy stránek vypočíst při minimálních nákladech.

Google PageRank má ale i své stinné stránky. Jeden příklad za všechny: je zaměřen hlavně na rozsáhlé a hustě prolinkované weby. U velkých konsorcií stačí do patičky objevující se na konci několika milionů stránek přidat nový odkaz a účinek je masivní. Menší weby ale takovou možnost nemají a tak, pokud se chtějí prosadit, obvykle shánějí zpětné odkazy po všech čertech, namísto aby se věnovaly tvoření a správě vlastního obsahu. Cestu z tohoto problému pro sebe našly blogy – svojí zásadou odkazovat na zdroje informací a na spřátelené blogy tvoří z pohledu výpočtu odkazových veličin shluk, který sám sebe výrazně posiluje.

Yuntis

Jiný přístup k počítání odkazových veličin použil vyhledavač Yuntis, který je výsledkem výzkumného projektu Maxima Lifantseva (který dříve pracoval na klasifikaci stránek pomocí metadat: OpenGRiD).

Yuntis namísto modelu náhodného uživatele používá „volební“ systém. Na počátku výpočtu mají stránky (resp. celé weby) přiděleny určité množství hlasů. Ty pak přidělují cílovým stránkám a nebo je předají dál, aby je cizí stránka přerozdělila za ně. PageRank je pouhou podmnožinou tohoto šířeji definovaného modelu, který je podle Maxima Lifantseva vhodnější kvůli tomu, že dobře konverguje (množství přerozdělovaných hlasů při každém průběhu klesá), je lépe chráněn proti zneužití a vytváří i další pomocné veličiny, které PageRank nezná. Také těch přibližně 15 procent, které u výpočtu PageRanku vyjadřují náhodné přeskočení uživatele, u Yuntisu není – možnost přerozdělovat si musí nějaký web „zasloužit“, není to pro všechny stejné.

Yuntis ve svém veřejně přístupném prototypu ukazuje tři veličiny:

• Reputation – vyjadřuje, jak hodnotná je stránka, pokud Yuntis považuje všechny odkazy jako podporu reputation a credibility.
• Credibility – vyjadřuje, jak důležitá/důvě­ryhodná je stránka při určování reputation a credibility všech stránek.
• Portality – vyjadřuje, jak snadné je z této stránky přes odkazy dosáhnout mnoho stránek s vysokou reputation.

Yuntis pracuje jak na úrovni jednotlivých stránek (URL), tak i na úrovni autorských oblastí – všechny tři výše uvedené veličiny počítá oběma způsoby. Více viz jeho výzkumné studie.

JyxoRank

České Jyxo, na kterém pracuji, také používá svůj způsob hodnocení stránek podle odkazů. Má některé společné znaky s výše uvedenými veličinami: Je počítané na základě všech odkazů v databázi (mimochodem, dnes ráno to bylo 776.115.456 hy­perlinků). A je počítané iterativně, tedy několika průchody.

Přináší ale ještě jeden nový koncept: dívá se, kdo na danou stránku odkazuje. Pokud máte tři odkazy na nějakou cílovou stránku, Google prostě sečte zlomky z PageRanků odkazujících stránek, a to je PageRank cílové stránky. Jyxo se ale raději podívá, co jsou ty tři stránky zač a co mají společného či rozdílného – zkoumá jejich domény a IP adresy. Pak preferuje hodnocení několika nezávislými zdroji.

Příklad z reálného života to objasní lépe: Pokud vám Petr, Dominika a Martin doporučí nějakou knihu, tak má toto hodnocení větší váhu, než když vám knihu doporučí sice jenom Petr, ale za to hned třikrát po sobě.

Takový výpočet je sice složitější na naprogramování i na hardware serveru (nestačí si jen zapsat jedno číslo, ale musíte si ještě pamatovat, kdo onu stránku již doporučil), ale výsledkem je spravedlivější ohodnocení dokumentů a z toho plynoucí větší přesnost vyhledávání. Největším přínosem je ale odolnost vůči zneužití. Milion stránek (které určitým způsobem odkazují na sebe navzájem i na nějakou cílovou stránku) si na webu může zřídit kdokoliv a pokud je Google zaindexuje, tak si tím onen člověk zvýší PageRank (díky bonusům z náhodných přeskoků, které jsou přímo úměrné počtu stránek). Zato pořídit si milion domén a IP adres prostě není ekonomicky výhodné.

Jak počítat rychleji

Nedávno vydali studenti na Stanfordu tiskovou zprávu, informující o některých technikách, které umožňují zrychlit výpočet PageRanku. Jsou to zčásti věci, které byly známé už pár let, nicméně zpráva získala nečekanou publicitu a dokonce i v Čechách se ji novináři pokoušeli několikrát interpretovat (z čehož vznikaly značně dadaistické výtvory, které kombinací špatného překladu, nepochopení a tvořivého domýšlení tvrdily něco zcela odlišného než původní zpráva).

Je to možná až příliš technické, ale abych nějak odčinil zmatení, které vyvolaly ostatní články, tak jen stručně vysvětlím, čeho se ona zrychlení týkala:

• BlockRank – stránky se na Internetu vyskytují v určitých shlucích (blocks), které jsou hustě prolinkované. Například zde na Lupě je mnoho odkazů na jednotlivé články, diskuse, archiv a některé služby. Odkazů mimo Lupu (nebo weby Internet Infa) je oproti nim málo. Studenti si tedy řekli – pojďme nejdřív spočítat ty odkazy v rámci jednoho webu, když je máme tak pěkně pohromadě, a pak teprve spočítáme vše ostatní s tím, že Lupu budeme brát jako jeden shluk. Takto je možné teoreticky zrychlit výpočet o 300 procent.
• Extrapolace – PageRank se normálně počítá několika průchody a jeho odhad se postupně zpřesňuje. Studenti udělali několik zjednodušujících předpokladů, které jim umožnily hádat dopředu (tedy rychleji).
• Adaptivní PageRank – některé hodnoty PageRanku se již při pozdějších průchodech příliš nemění a tak je možné je přeskočit a soustředit se na to, co ještě nebylo spočítáno.

Tato zrychlení se netýkají Google (je to nezávislý výzkum) ani neovlivňují rychlost vyhledávání.

Zkuste si sami

Nedokážete-li si představit, jak takové propojení webu pomocí odkazů vypadá, můžete se prostě podívat na obrázek z galerie Hala Burche:

Pokud je vám líto, že nevlastníte žádný vyhledavač a tak si nemůžete hrát s počítáním PageRanků, zkoumat strukturu propojení webu nebo vytvářet podobné obrázky, tak se podívejte na WebGraph. Odtud si můžete stáhnout nějaké programy, ale hlavně seznam odkazů mezi sto miliony dokumentů. Velmi zajímavé je, že seznam je zkomprimován na pouhé tři bity na odkaz (!). K docílení takového zmenšení byla použita myšlenka obdobná výše uvedenému BlockRanku – stránky tvoří shluky a je možné použít méně bitů na zapsání odkazů na blízké stránky.