Algoritmus hodnotenia odkazov PageRank a lineárna algebra. Algoritmy hodnotenia Yandex: História vývoja Algoritmy hodnotenia Yandex

PageRank je číselná hodnota, ktorá charakterizuje „dôležitosť“ webovej stránky. Čím viac odkazov vedie na stránku lokality a čím sú kvalitnejšie, tým sa stránka stáva „dôležitejšou“. Okrem toho je „váha“ stránky A určená váhou odkazu prenášaného stránkou B. PageRank je teda metóda výpočtu váhy stránky vypočítaním dôležitosti odkazov na ňu.

Túto metódu výpočtu patentovali vývojári a spoluzakladatelia vyhľadávacieho nástroja Google Sergey Brin a Larry Page. Prečítajte si text štúdie podrobnejšie (v angličtine). V ruštine .

Aká je váha webovej stránky?

Pod váhou stránky je miera jej dôležitosti. Ak nakreslíme analógiu s ľudskými vzťahmi, potom fráza „jeho slovo má váhu“ bude odrážať podstatu pojmu „váha webovej stránky“.

Hmotnosť stránky je vyjadrená v konkrétnych číslach a dá sa vypočítať.

Bežne existujú dva typy hmotnosti stránky:

1. Statická váha (určité číslo), ktorá sa vypočítava na základe faktorov nezávislých od dopytu – to všetko sú faktory, ktoré nesúvisia s vyhľadávacím dopytom. Napríklad vek stránky, jej stránky, dátum indexovania stránok, počet interných a externých odkazov vedúcich na stránku.
2. Dynamická váha, ktorá sa vypočítava na základe faktorov závislých od dopytu – to všetko sú faktory, ktoré sú spojené s vyhľadávaným dopytom (textom). Text požiadavky sa porovnáva s textom stránky webu, preto faktory závislé od požiadavky sú tie, ktoré primárne závisia od textových prvkov stránky – jej nadpisu, popisu, textu na nej, ukotvení (textov) odkazov, ktoré poukazujú naň a vychádzajú z neho.

Algoritmus PageRank určuje statickú váhu stránky, nie dynamickú. Inými slovami, statická váha stránky je jej PageRank. Na webe môže byť stránka bez obsahu, no ak na ňu vedie aspoň jeden odkaz, tak bude mať statickú váhu.

Statická váha je posudzovaná vyhľadávacími nástrojmi na pozadí a priradená stránke webu. Po určitom čase sa prepočíta. Dynamická váha sa nevypočítava na pozadí, ale za behu, keď používateľ odošle vyhľadávací dopyt do vyhľadávača, aby našiel výsledky.

Ako vyzerá vzorec PageRank?

Nikto presne nevie, ako Google v skutočnosti počíta PageRank. Môžete sa však zamerať na tento vzorec, ktorý navrhli Sergey Brin a Larry Page vo svojej štúdii.

PR(A)=(1-d)+d(PR(T_1)/C(T_1) +⋯+PR(T_n)/C(T_n)) , Kde

PR(A) - váha stránky akceptora A (na ktorú je umiestnený odkaz)

PR(T_n) - váha stránky darcu odkazujúcej na stránku A (z ktorej je odkaz umiestnený)

C(T_n) - počet odkazov zo stránky darcu

D je koeficient útlmu, zvyčajne sa rovná 0,85. V pravdepodobnostnom modeli to znamená, že používateľ vôbec nebude nasledovať odkaz, ale zatvorí stránku lokality. Tejto udalosti bola priradená pravdepodobnosť 15 %. Zvyšných 85 % pripadá na odkazy.

1-d je prvok, ktorý je potrebný na zabezpečenie toho, aby sa vzorec nestal nulovým, ak sa váha odkazujúcich darcovských stránok rovná 0. To znamená, že aj tá najnevýznamnejšia stránka na webe môže preniesť určitú minimálnu váhu prostredníctvom odkazu. .

Vzorec môže byť napísaný nasledovne

Váha stránky príjemcu lokality sa rovná súčtu váh prenášaných prostredníctvom odkazov z donorských stránok na stránku príjemcu.

Príklad

Ak je webová stránka propagovaná v oblasti predaja roliet, musíme nájsť stránky na darcovských stránkach s vysokým PageRankom. Pri outreachingu neanalyzujem hodnotu PageRank každej stránky webu, s ktorou chcem dosahovať, pretože... takáto stránka môže byť na spamovanom webe. Zameriavam sa na tému darcovskej stránky a na to, aby bola takáto stránka vo vyhľadávači TOP 10 na tematické informačné dopyty, ktoré sa týkajú propagovaného produktu/služby a na ukazovatele, podľa ktorých kontrolujem každú stránku potenciálneho darcu pred napísaním návrhu. jeho vlastníkovi alebo osobe zodpovednej za uverejňovanie materiálov na ňom, o zverejnení odkazu alebo zmienky.

Ak je stránka na prvej stránke s výsledkami vyhľadávania, vyhľadávací algoritmus ju považoval za kvalitnú, aby bola v TOP 10 pre vyhľadávací dopyt, ktorý nás zaujíma. Mali by ste sa pokúsiť získať aktívny odkaz alebo zmienku z takejto stránky, pretože už má návštevnosť z vyhľadávania a odkaz umiestnený na takejto stránke bude mať vysokú pravdepodobnosť, že ho používatelia budú sledovať kvôli umiestneniu v TOP.

Vydali sme novú knihu Marketing obsahu sociálnych médií: Ako sa dostať do hláv svojich nasledovníkov a prinútiť ich, aby sa zamilovali do vašej značky.

Ranking algorithms - metódy hodnotenia kvality webových stránok

TOP 10 by malo zahŕňať iba tie stránky, ktoré čo najúplnejšie odpovedajú na požiadavku používateľa. Vysokokvalitné výsledky zaisťujú špeciálne matematické vzorce, ktoré určujú „užitočnosť“ konkrétnej lokality. Vyhľadávače nezverejňujú informácie o svojich algoritmoch, poskytujú webmasterom iba všeobecné odporúčania na zlepšenie a optimalizáciu stránok. Optimalizátori sa však naučili identifikovať určité vzory, na základe ktorých sa vyvíja stratégia.

pohyb.

Viac videí na našom kanáli - naučte sa internetový marketing so SEMANTICOU

Aké kritériá zohľadňuje algoritmus hodnotenia?

Vyhľadávače hodnotia webové stránky na základe mnohých parametrov. Medzi najvýznamnejšie kritériá patria:

• jedinečnosť a optimalizácia textov (prítomnosť kľúčových fráz, nevoľnosť, obsah vody);
• vek domény;
• množstvo a kvalita prichádzajúcich odkazov;
• typ použitého CMS;
• rýchlosť načítania stránky;
• prítomnosť chýb v kóde.

Pochopením toho, ako funguje algoritmus vyhľadávacieho nástroja, môže správca webu ovplyvniť hodnotenie svojej webovej stránky. K tomu je potrebné „prispôsobiť“ stránky webového projektu požiadavkám PS. Najmä budete musieť vložiť kľúčové frázy do metaznačiek názvu a popisu, ako aj priamo do textu stránky. Ak propagujete na základe geograficky závislej požiadavky, mali by ste okrem kľúčov pridať aj názov požadovaného mesta alebo regiónu.

Toto je zaujímavé! Vyhľadávací nástroj sa pravidelne aktualizuje, čo vedie k radikálnej zmene existujúcich algoritmov. Takéto opatrenia sú zamerané na boj proti vyhľadávaciemu spamu. Zmena v algoritme Yandex často vedie k zhoršeniu pozícií stránok propagovaných „čiernymi“ a „sivými“ metódami.

Hľadaj sankcie

Ak sa správca webu zjavne pokúša manipulovať s algoritmami Yandex, vyhľadávací nástroj na neho môže uplatniť rôzne sankcie. Môžu sa vyskytnúť nasledujúce problémy:

• Nižšie pozície vo výsledkoch vyhľadávania
• Zlé indexovanie nových stránok (alebo strata starých dokumentov z indexu)
• Úplný alebo čiastočný BAN

Algoritmy Yandex ukladajú sankcie za nadmernú optimalizáciu textov, napríklad za zverejňovanie zoznamov kľúčových fráz na stránkach. Filter je možné použiť tak, aby sa "neviditeľný" text prelínal s pozadím. Sankciám podliehajú aj portálové stránky a internetové platformy, ktoré kopírujú obsah iných ľudí.

Nový algoritmus Yandex – Minusinsk

Tento algoritmus zahŕňa pesimizáciu webového projektu na používanie odkazov SEO. Hovoríme o stránkach, ktoré nakupujú tisíce odkazov pomocou automatizovaných výmen, ako je Sape. Z pohľadu Yandexu sa odkaz považuje za „SEO“, ak vedie z nekvalitnej darcovskej stránky a má komerčnú kotvu.

Dôvodom použitia filtra „ “ môže byť prudký nárast hmotnosti spoja. Preto, aby ste ochránili svoj webový projekt pred možnosťou takejto sankcie, mali by ste kupovať odkazy postupne a riediť kotviace odkazy nekotvovými hypertextovými odkazmi.

Celkom

Po veľmi dlhú dobu zostali hodnotiace algoritmy Yandex pre používateľov „tajomstvom“. Špecialisti na vyhľadávače Yandex radšej neinformovali používateľov internetu o zmenách v algoritmoch hodnotenia.

Algoritmy hodnotenia Yandex

1 2007

A až v roku 2007 začali zamestnanci spoločnosti Yandex informovať svojich používateľov o zavedení inovácií do vyhľadávacieho algoritmu. Vďaka tomu je propagácia webových stránok pre mnohých webmasterov o niečo jednoduchšia.

Stojí za zmienku, že algoritmy hodnotenia Yandex sa neustále menia. Vďaka týmto zmenám pribúda novšia a pokročilejšia funkcionalita, ktorá značne uľahčuje prácu s týmto vyhľadávačom. Vďaka zmenám v algoritmoch hodnotenia sa tiež odstránia chyby, aktualizujú sa filtre a obmedzovače a upraví sa presnejšie doručovanie informácií, ktoré najlepšie zodpovedajú pôvodnej požiadavke.

2. mája 2008

V máji 2008 vydali špecialisti Yandex nový algoritmus s názvom „Magadan“.

Magadanov algoritmus

V tomto algoritme sa zdvojnásobil počet hodnotiacich faktorov a výrazne sa zlepšil klasifikátor na základe polohy používateľa (geografické zacielenie). Aj v algoritme Magadan existujú také inovatívne riešenia, ako je pridávanie klasifikátorov pre obsah a odkazy. Výrazne sa zvýšila rýchlosť vyhľadávača pri vyhľadávaní informácií na základe zadaných kľúčových dopytov (vďaka tomuto algoritmu je vyhľadávač schopný poskytnúť informácie aj s textami, ktoré majú predrevolučný pravopis).

V júli toho istého roku bola vydaná nová verzia Magadanského algoritmu, ktorá zahŕňala ďalšie hodnotiace faktory, napríklad určenie jedinečnosti textu a informácií, určenie, či je obsah pornografický atď.

3. septembra 2008

Už v septembri 2008 spoločnosť Yandex vydala nový algoritmus s názvom „Nakhodka“.

Vďaka nástupu tohto algoritmu sa výrazne zlepšila práca so slovníkmi vo vyhľadávacom systéme Yandex a výrazne sa zvýšila kvalita hodnotenia pre dopyty, ktoré obsahujú zastavovacie slová (spojky a predložky). V tomto algoritme bol tiež vyvinutý úplne nový prístup k strojovému učeniu (stroj začal rozlišovať medzi rôznymi dopytmi a začal meniť faktory hodnotenia pre rôzne dopyty vo vzorci výpočtu pre výsledky vyhľadávania).

4. apríla 2009

Nový algoritmus s názvom „Arzamas“ alebo „Anadyr“ bol zverejnený vo vyhľadávacom nástroji Yandex v apríli 2009.

Arzamasov algoritmus

Vďaka zavedeniu tohto algoritmu sa vyhľadávací nástroj Yandex naučil presnejšie a výrazne lepšie porozumieť ruskému jazyku, čo umožnilo presnejšie vyriešiť nejednoznačné slová v dopytoch. Tento algoritmus tiež umožnil vyhľadávaču zohľadniť región, v ktorom sa používateľ nachádza. Používatelia vďaka tomu začali dostávať presnejšie a užitočnejšie informácie o žiadanej problematike, ktoré boli najrelevantnejšie pre región, v ktorom sa používateľ nachádzal.

Je potrebné poznamenať, že v rôznych regiónoch sa aj poskytnuté informácie líšia, a to aj napriek rovnakému dopytu zadanému používateľom. Aj v tomto vyhľadávacom algoritme bol vzorec výrazne vylepšený, čo uľahčuje prácu s viacslovnými dopytmi. Prísnejšie filtre boli zavedené pre stránky s popunder bannermi (banner Pop-Under sa zobrazuje na všetkých stránkach webu a nesúvisí s témou webu), clickander (reklama typu Click-under, ktorá sa zobrazí na stránke, keď návštevník prvýkrát klikne) a bodyclic (Bodyclic – reklamná služba s ukážkami).

5. novembra 2009

V novembri 2009 bol vydaný nový algoritmus, ktorý sa nazýva „Snezhinsk“.

Algoritmus Snezhinsk

Tento algoritmus zavádza ďalšie funkcie a parametre hodnotenia, ktoré vám umožňujú použiť niekoľko tisíc parametrov vyhľadávania pre jeden dokument. Aj v tomto algoritme boli zavedené nové regionálne parametre (filtre pre stránky zámerne sa snažiace ovplyvniť výsledky vyhľadávania, jednoduchšia, anti-shit stránka) a výrazne sa zlepšilo vyhľadávanie pôvodného obsahu na internete. Tento algoritmus zahŕňal aj samoučiaci sa systém MatrixNet.

6. december 2009

V decembri 2009 sa objavil nový algoritmus s názvom „Konakovo“.

Tento algoritmus bol len vylepšenou verziou algoritmu Snezhinsk a zlepšilo sa iba lokálne hodnotenie. V septembri 2010 bol vydaný nový algoritmus „Obninsk“. V tomto algoritme sa zlepšilo hodnotenie pre územne nezávislé dopyty a zaviedlo sa obmedzenie vplyvu umelých odkazov na hodnotenie. Aj vďaka tomuto algoritmu sa výrazne zlepšil postup určovania autorského textu a výrazne sa rozšíril transliteračný slovník.

7 2010

V decembri 2010 bol vydaný nový algoritmus s názvom „Krasnodar“.

Na vytvorenie tohto algoritmu bola špeciálne vyvinutá nová technológia s názvom Spectrum. Vďaka tomuto algoritmu začal vyhľadávací nástroj Yandex klasifikovať dopyty a vyberať z nich objekty a priraďovať dopytom konkrétnu kategóriu (produkty, služby atď.).

8 2014

Ďalší zabijácky výstrel od Yandexu – hodnotiace algoritmy Yandex už nebudú pri hodnotení zohľadňovať odkazy. Podľa najnovších oznámení bude hodnotenie bez prepojenia spustené začiatkom roka 2014. Yandex odstráni všetky faktory prepojenia z faktorov hodnotenia. Táto inovácia ovplyvní iba komerčné požiadavky a bude najskôr testovaná v Moskve a Moskovskom regióne. Autori inovácií, tvorcovia AGS Yandex.

Okrem grafických a množinovo-teoretických často využívajú algebraická reprezentácia graf v maticovej forme.

Zvážte digraf G obsahujúce n vrcholy a m rebrá Matica susedstva digraf G nazývaná matica A veľkosť n n

Niekedy sa nazýva matica susedstva matice vzťahov, alebo matice priamych spojení.

Matica incidencie(alebo incidentová matica) digraf G nazývaná matica B veľkosť n m, v ktorom

Ak chcete zaviesť maticu susednosti, musíte očíslovať vrcholy a pre maticu výskytu okraje grafu.

Algebraická reprezentácia nám umožňuje algoritmizovať vo forme vhodnej pre počítačové programovanie postup určovania štrukturálnych kvantitatívnych parametrov systému.

Uvažujme teraz o niektorých metódach riešenia praktických problémov pomocou matematického formalizmu, ktorý sme zaviedli.

Hodnotenie prvkov systému

Analýza súvislostí v grafe spočíva predovšetkým v hľadaní a vyhodnocovaní ciest medzi jeho vrcholmi. Okrem priameho hľadania cesty v určitom komunikačnom systéme tento problém zahŕňa napríklad problém výberu optimálnej stratégie a pod.. V skutočnosti stačí priradiť vrcholy grafu k nejakým cieľom a dĺžky cesty s nákladmi na dosiahnutie týchto cieľov s cieľom získať problém výberu stratégie na dosiahnutie cieľa s čo najnižšími nákladmi.

Hľadanie ciest pomocou výkresu so zložitou štruktúrou grafu (v praxi musíte analyzovať grafy s viac ako 100 vrcholmi) je náročné a je spojené s možnosťou chýb. Zoberme si jednu z algebraických metód, ktorá je vhodná na použitie na počítači. Táto metóda umožňuje na základe matice priamych spojení , stavať matica plnej cesty
, Kde - počet ciest z vrcholu i navrchol j(= 0), alebo sa obmedzíme na nájdenie jedného z jeho prvkov.

čísla alebo ich doslovné výrazy sú určené pomocou špeciálneho druhu kvalifikátora - kvázi neplnoletí(nepodpísanédeterminanty). Vzorec platí

.

Výraz
volal kvázi vedľajší prvokmatice . Podpísať
je kvázi vedľajší symbol a
ukazuje na maticu s preškrtnutým l riadok a k stĺpec, ktorý zapadá do kvázi-vedľajšieho symbolu ako matica, ktorá zapadá do symbolu obyčajného minoru.

Výpočet kvázi-malej položky sa redukuje na jej rozklad na kvázi-menšie položky nižšieho rádu podľa vzorca

Postup výpočtu je v mnohom podobný postupu pri výpočte konvenčných determinantov, no zvládnutie tejto metódy si vyžaduje určitú zručnosť.

Príklad.

Matica priamych spojení nech má tvar

Je potrebné nájsť všetky cesty vedúce od vrcholu 1 po 5 a spočítať ich počet.

Pre uvažovaný príklad dostaneme

Pôvodne v matrice Stĺpec 1, zodpovedajúci číslu vrcholu, z ktorého cesta začína, a riadok 5, zodpovedajúci číslu vrcholu, v ktorom cesta končí, sa prečiarknu. To zodpovedá odstráneniu z grafu všetkých hrán vedúcich k vrcholu 1 a opusteniu vrcholu 5. Pozíciu a číslovanie zostávajúcich riadkov a stĺpcov je vhodnejšie ponechať nezmenené. Ďalej je potrebné výsledný kvázi-vedľajší prvok rozvinúť na nenulové prvky 1. riadku

Rozšírenie pre prvý termín sa vykonáva na druhom riadku, druhý - na treťom, tretí - na štvrtom, t.j. číslo riadku, na ktorom sa uskutočňuje rozšírenie, sa rovná číslu stĺpca, v ktorom sa nachádzal posledný termín rozšírenia.

Ak teraz dáme za nenulové prvky = 1 a vykonávame operácie podľa pravidiel bežnej aritmetiky, dostaneme -
.

Ak vo výslednom výraze vykonáme akcie podľa pravidiel Booleovej algebry, získame hodnotu kompletná matica spojení, ktorý charakterizuje grafová konektivita. Hodnoty prvkov kompletnej matice pripojenia sú definované takto:

= 1, ak je vrchol i spojený s vrcholom j aspoň jednou cestou,

=0 inak.

Zvyčajne sa tomu verí
.

Konektivita je najdôležitejšou charakteristikou štruktúrneho diagramu systému. Čím lepšia je úplnosť kompletnej matice spojení, tým lepšia je štruktúra. Prítomnosť veľkého počtu núl naznačuje vážne chyby v štruktúre systému.

Ďalšou dôležitou charakteristikou štruktúry je rozdelenie dôležitosti prvkov systému. Kvantitatívna charakteristika významu - hodnosť prvku- bol prvýkrát explicitne formulovaný pri analýze štruktúry vzťahov dominancie (nadradenosť, prevaha) v skupinách jednotlivcov (ľudí, zvierat).

Použitie matice celej cesty
, hodnoty poradia prvkov sú určené vzorcom

.

Treba mať na pamäti, že význam prvku nie je určený samotnou hodnotou , ale porovnaním radov všetkých prvkov, t.j. hodnosť je relatívny ukazovateľ dôležitosti.

Čím je daný prvok vyšší, tým väčší je počet ciest, ktoré sú spojené s inými prvkami, a tým väčší je počet prvkov, ktorých normálne prevádzkové podmienky budú narušené, ak dôjde k jeho zlyhaniu. Preto pri vytváraní programu na zabezpečenie spoľahlivosti posudzovaného systému je potrebné venovať osobitnú pozornosť prvkom s vysokou hodnosťou.

V prípade systémov so štruktúrou sieťového typu prítomnosť prvkov s výrazne vyšším poradím ako ostatné zvyčajne naznačuje funkčné preťaženie týchto prvkov. Odporúča sa prerozdeliť pripojenia a poskytnúť riešenia, aby sa vyrovnala dôležitosť prvkov daného systému.

Existujú aj iné metódy na určenie hodností. Výber vhodnej techniky je určený špecifikami úlohy.

Treba poznamenať, že existujú štruktúry, ktorých poradie prvkov môže stratiť praktický význam. V prvom rade ide o hierarchické štruktúry. Význam prvku v nich je určený úrovňou hierarchie.

Autor rozpráva okolo 30 zábavných (a poučných) príbehov z oblasti matematiky. Jeden z príbehov hovorí o princípoch PageRank, algoritmu hodnotenia odkazov, ktorý prvýkrát použil Google. Téma je relevantná a celkom ľahko pochopiteľná. Takže k Stevenovi Strogatzovi...

V tých vzdialených časoch, keď Google ešte neexistoval, bolo vyhľadávanie na internete beznádejnou úlohou. Stránky ponúkané staršími vyhľadávačmi často nezodpovedali dopytu a tie, ktoré obsahovali potrebné informácie, boli buď zahrabané hlboko v zozname výsledkov, alebo úplne chýbali. Algoritmy založené na analýze odkazov vyriešili problém tým, že sa dostali k jadru paradoxu podobného zenovým koanom: vyhľadávanie na internete malo ukázať tie najlepšie stránky. Čo robí stránku lepšou? Keď na to odkazujú iné rovnako dobré stránky.

Stiahnite si poznámku v alebo

Znie to ako začarovaný kruh. Toto je pravda. Preto je všetko také komplikované. Algoritmus dolovania odkazov využíva túto myšlienku a využíva ju vo svoj prospech a poskytuje riešenie jiu-jitsu pre vyhľadávanie na webe. Tento prístup je založený na myšlienkach prevzatých z lineárnej algebry, štúdia vektorov a matíc. Či už chcete identifikovať vzory v obrovských množstvách údajov alebo vykonávať gigantické výpočty zahŕňajúce milióny premenných, lineárna algebra vám poskytne nástroje, ktoré potrebujete. S jeho pomocou bol vybudovaný základ pre algoritmus PageRank, ktorý tvorí základ Google. Pomohla tiež vedcom klasifikovať ľudské tváre, analyzovať hlasovanie na Najvyššom súde a vyhrať cenu Netflix (udelenú tímu, ktorý môže zlepšiť systém Netflixu na vytváranie odporúčaní pre najlepšie filmy o viac ako 10 percent).

Ak chcete preskúmať lineárnu algebru v praxi, pozrime sa, ako funguje algoritmus PageRank. A aby sme bez zbytočného rozruchu odhalili jeho podstatu, predstavme si hračkársky web pozostávajúci len z troch vzájomne prepojených stránok takto:

Ryža. 1. Malá sieť troch lokalít

Šípky označujú, že stránka X obsahuje prepojenie na stránku Y, ale Y nie je opätované. Naopak, Y sa vzťahuje na Z. Zatiaľ, X a Z sa navzájom týkajú.

Ktoré stránky sú na tomto malom webe najdôležitejšie? Možno si myslíte, že to nie je možné určiť pre nedostatok informácií o ich obsahu. Ale tento spôsob myslenia je zastaraný. Obavy o obsah viedli k nepohodlnému spôsobu hodnotenia stránok. Počítače málo rozumejú obsahu a ľudia si nevedia poradiť s tisíckami nových stránok, ktoré sa denne objavujú na internete.

Prístup, ktorý vymysleli Larry Page a Sergey Brin, postgraduálni študenti univerzity a zakladatelia spoločnosti Google, spočíval v tom, že umožnili stránkam zoradiť sa v určitom poradí hlasovaním o odkazoch. Vo vyššie uvedenom príklade stránky X a Y odkazujú na Z, vďaka čomu je Z jediná stránka s dvomi prichádzajúcimi odkazmi. V dôsledku toho to bude najobľúbenejšia stránka v tomto prostredí. Ak však odkazy pochádzajú zo stránok pochybnej kvality, budú pracovať proti sebe. Popularita sama o sebe nič neznamená. Hlavná vec je mať odkazy z dobrých stránok.

A tu sa opäť ocitáme v začarovanom kruhu. Stránka je dobrá, ak má dobré stránky, ktoré na ňu odkazujú, ale kto rozhodne, ktoré z nich sú dobré? O tom rozhoduje sieť. Tak to chodí.

Algoritmus Google priraďuje každej stránke zlomkové číslo medzi 0 a 1. Táto číselná hodnota sa nazýva PageRank a meria „dôležitosť“ stránky v porovnaní s ostatnými vypočítaním relatívneho času, ktorý by hypotetický používateľ strávil jej návštevou. Aj keď si používateľ môže vybrať z viac ako jedného odchádzajúceho odkazu, vyberie si jeden náhodne s rovnakou pravdepodobnosťou. Pri tomto prístupe sa stránky považujú za smerodajnejšie, ak sú navštevované častejšie.

A keďže indexy PageRank sú definované ako proporcie, ich súčet v celej sieti musí byť 1. Tento zákon zachovania navrhuje ďalší, možno hmatateľnejší spôsob vizualizácie PageRank. Predstavte si to ako tekutú látku prúdiacu sieťou, ktorej množstvo na zlých stránkach klesá a na dobrých stúpa. Pomocou algoritmu sa snažíme určiť, ako sa táto tekutina v priebehu času distribuuje na internete.

Odpoveď získate ako výsledok nasledujúceho procesu, ktorý sa mnohokrát opakuje. Algoritmus začína odhadom, potom aktualizuje všetky hodnoty PageRank, pričom tekutinu rovnomerne rozdelí medzi odchádzajúce odkazy a potom iteruje cez niekoľko kôl, kým nedosiahne určitý stav, kedy stránky získajú svoj spravodlivý podiel.

Na začiatku algoritmus nastaví rovnaké podiely, čo umožňuje každej stránke získať rovnakú hodnotu PageRank. V našom príklade sú tri stránky a každá z nich sa začne pohybovať podľa algoritmu so skóre 1/3.

Ryža. 2. Počiatočné hodnoty PageRank

Skóre sa potom aktualizuje, aby zobrazovalo skutočnú hodnotu každej stránky. Pravidlom je, že každá stránka si vezme hodnotenie PageRank z posledného kruhu a rovnomerne ho rozdelí na všetky stránky, na ktoré odkazuje. Preto je aktualizovaná hodnota stránky X po prvom kole stále 1/3, pretože toľko PageRanku dostane od Z, jedinej stránky, ktorá na ňu odkazuje. Tým sa zníži skóre stránky Y na 1/6, pretože po predchádzajúcom kole získa iba polovicu PageRanku X. Druhá polovica ide na stránku Z, čím sa v tomto bode stáva víťazom, pretože k sebe pridáva ďalšiu 1/6 strany X, ako aj 1/3 Y, spolu teda 1/2. Po prvom kruhu teda máme nasledujúce hodnoty PageRank:

Ryža. 3. Hodnoty PageRank po jednej aktualizácii

V nasledujúcich kruhoch zostáva pravidlo aktualizácie rovnaké. Ak označíme x, y, z aktuálny počet strán X, Y a Z, potom ako výsledok aktualizácie dostaneme nasledujúci počet:

z’ = ½ x + y,

kde ťahy označujú, že došlo k aktualizácii. Takéto opakované výpočty je vhodné vykonávať v tabuľkovom procesore (alebo ručne, ak je sieť malá, ako v našom prípade).

Po desiatich opakovaniach zistíme, že čísla sa od aktualizácie k aktualizácii prakticky nemenia. V tomto bode bude podiel X 40,6 % z celkového PageRanku, podiel Y bude 19,8 % a Z bude 39,6 %. Tieto hodnoty sú podozrivo blízke číslam 40, 20 a 40 %, čo naznačuje, že algoritmus by sa k nim mal približovať. Toto je pravda. Algoritmus Google definuje tieto limitné hodnoty pre sieť ako PageRank.

Ryža. 4. Obmedzenia hodnotenia PageRank

Záver pre túto malú sieť je taký, že stránky X a Z sú rovnako dôležité, aj keď Z má dvakrát toľko prichádzajúcich odkazov. Je to pochopiteľné: Stránka X sa rovná dôležitosti Z, pretože od nej dostáva úplný súhlas, ale na oplátku jej dáva iba polovicu. Druhá polovica ide Y. To tiež vysvetľuje, prečo Y dostane len polovicu akcií X a Z.

Je zaujímavé, že tieto hodnoty je možné získať bez použitia viacerých iterácií. Stačí sa zamyslieť nad podmienkami, ktoré definujú stacionárny stav. Ak sa po ďalšej aktualizácii nič nezmení, potom x’ = x, y’ = y a z’ = z. Preto nahradením primárnych premenných v aktualizačných rovniciach ich ekvivalentmi bez prvočísel získame systém rovníc

pri riešení x = 2y = z. Keďže súčet hodnôt x, y a z sa musí rovnať 1, z toho vyplýva, že x = 2/5, y = 1/5 a z = 2/5, čo zodpovedá predtým zisteným hodnotám.

Ťažkosti začínajú tam, kde je v rovniciach obrovské množstvo premenných, ako sa to stáva v reálnej sieti. Preto je jedným z ústredných problémov lineárnej algebry vývoj rýchlejších algoritmov na riešenie veľkých sústav rovníc. Dokonca aj menšie vylepšenia v týchto algoritmoch sú citeľné takmer vo všetkých oblastiach života – od letových poriadkov až po kompresiu obrazu.

Najvýznamnejším víťazstvom lineárnej algebry, pokiaľ ide o jej úlohu v každodennom živote, však bolo určite riešenie zenového budhistického paradoxu pre hodnotenie stránok. „Stránka je len taká dobrá, ako dobré stránky, ktoré na ňu odkazujú.“ Preložené do matematických symbolov sa toto kritérium stáva algoritmom PageRank.

Vyhľadávač Google sa stal tým, čím je dnes, vyriešením rovnice, ktorú sme práve vyriešili vy a ja, ale s miliardami premenných – a teda s miliardovými ziskami.

Podľa Google výraz PageRang pochádza z mena jedného zo zakladateľov Google Larryho Pagea a nie z anglického slova page (page).

Pre jednoduchosť uvediem iba základnú verziu algoritmu PageRank. Aby bolo možné zvládnuť siete s niektorými ďalšími štrukturálnymi vlastnosťami, je potrebné ho upraviť. Predpokladajme, že v sieti existujú stránky, ktoré odkazujú na iných, ale tie na ne neodkazujú. Počas procesu aktualizácie tieto stránky stratia hodnotenie PageRank. Dávajú ho iným a už sa nedopĺňa. Skončia teda s hodnotami PageRank rovnými nule a z tohto hľadiska sa stanú nerozoznateľnými.

Na druhej strane existujú siete, kde sú niektoré stránky alebo skupiny stránok otvorené na zhromažďovanie hodnotenia PageRank, ale neodkazujú na iné stránky. Takéto stránky fungujú ako akumulátory PageRank.

Aby sa zabránilo takýmto výsledkom, Brin a Page upravili svoj algoritmus nasledovne. Po každom kroku procesu aktualizácie údajov sa všetky aktuálne hodnoty PageRank znížia o konštantný faktor, takže ich súčet je menší ako 1. Potom sa zostávajúci PageRank rovnomerne rozdelí medzi všetky uzly v sieti, akoby „spadol z obloha." Algoritmus teda končí vyrovnávacou akciou, ktorá rozdeľuje hodnoty PageRank medzi najchudobnejšie uzly.

O matematike PageRank a interaktívnom výskume podrobnejšie pojednávajú E. Aghapour, T. P. Chartier, A. N. Langville a K. E. Pedings, Google PageRank: The mathematics of Google (