Markovo procesai → „PageRank“ algoritmas → „Google“ (0)

2012-01-23

1998 m. Stanfordo (Kalifornija, JAV) universiteto studentai Larry Page‘as ir Sergejus Brinas vykdė tyrimų projektą apie naujos kartos internetinės paieškos variklius. To meto internetinės paieškos sistemos tinklapius vertino (rangavo) pagal tai, kiek kartų vykdoma užklausa aptikta tame tinklapyje.

Prisijunk prie technologijos.lt komandos!

Laisvas grafikas, uždarbis, daug įdomių veiklų. Patirtis nebūtina, reikia tik entuziazmo.

Sudomino? Užpildyk šią anketą!

. L.Page‘ui ir S.Brinui kilo idėja, puslapiuose esančią informaciją surikiuoti pagal tai, kiek nuorodų (saitų) yra nukreipta į šį puslapį (puslapio rangas didesnis, kuo daugiau nuorodų į jį yra). Naujasis algoritmas buvo pavadintas PageRank ( page – angl., puslapis, be to vieno iš algoritmo atradėjų pavardė). Kalbant Markovo procesų terminais, bet kokia susietų dokumentų sistema (pavyzdžiui žiniatinklis) gali būti laikoma Markovo procesu: tinklapis – sistemos būsena, nuoroda – perėjimas tarp būsenų. Konkretaus tinklapio PageRank indekso reikšmė išreiškia tikimybę, kad atsitiktinis naršytojas atsitiktinai spausdamas vieną nuorodą po kitos galiausiai atsidurs šiame puslapyje. Ši tikimybė yra lygi 1/n ; čia n – vidutinis paspaudimų skaičius, kol atsitiktinis naršytojas atsidurs reikiamame puslapyje. atvirkštinis dydis. Tokios ilgo laikotarpio tikimybės dar vadinamos stacionariosiomis tikimybėmis. Tinklapio PageRank indekso reikšmė kinta nuo 0 (mažiausios svarbos) iki 10 (didžiausios svarbos). Kuo daugiau nuorodų (nuorodos iš puslapių su aukštesniu PageRank turi didesnį svorį) nukreipta į tinklapį, tuo didesnis puslapio PageRank indeksas. Teigiama kad pasiekti 3-4 indeksą pakanka nedidelio kiekio nuorodų. Tuo tarpu aukščiausią 10 PageRank reikšmę pasiekia tik nedaugelis tinklapių, pvz. pasaulinės reikšmės organizacijų ir valdžios įstaigų (Baltieji rūmai JAV, NASA) ar didžiosios internetinės kompanijos (Google, Facebook).

Nors PageRank algoritmas gali būti pritaikytas bet kokioms nuorodomis susietų dokumentų sistemoms, bet neabejotinai žymiausias PageRank pritaikymo pavyzdys – „Google“ paieškos sistema. Šiuo metu „PageRank“ yra „Google“ korporacijos prekinis ženklas. Visa PageRank skaičiavimo procedūra yra užpatentuota ir saugoma Jungtinių Valstijų patento nr. 6 285 699 (patentas priklauso Stanfordo universitetui, tačiau „Google inc.“ turi išskirtines naudojimo teises).

Taigi, naudodami Markovo procesų teoriją, S.Brinas ir L.Page‘as sukūrė PageRank algoritmą, PageRank padėjo pagrindą „Google“ paieškos sistemai ir „Google“ korporacijai, kuri pateikiama kaip viena žymiausių sėkmės istorijų versle.

Beje, Google pavadinimas kilo iš netaisykl. angl. googol – tai skaičius, turintis simbolizuoti milžiniškus duomenų kiekius, kuriuos gebės apdoroti naujoji sistema. Tačiau dabar bendriniu anglų kalbos žodžiu tapęs google, vartojamas kur kas dažniau negu googol.

Internetinis Kauno technologijos universiteto tinklapio www.ktu.lt PageRank indeksas yra 8. Aukštesniu nei 8 PageRank indeksu kol kas negali pasigirti nei vienas domenas su galūne .lt . Pvz., populiarių naujienų portalų kaip pvz. delfi.lt ar lrytas.lt PageRank indeksas yra 7.

Pasidalinkite su draugais

Aut. teisės: www.technologijos.lt
Autoriai: Mindaugas Šnipas

(0)

Komentarai (0)