TokiTetel39

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Oldalak rangsorolása webes keresőrendszerekben

A rengeteg weboldalt egy fontossági sorrendbe kell sorolni, hogy lehessen köztük keresni. A Google a Pagerank algoritmusának működése: Annál fontosabb egy oldal, minél több (minél fontosabb) oldal linkel rá. A linkek egyik lapról a másikra mutatnak, vagyis egyik állapotból a másikba, így felfoghatjuk homogén Markov-láncként is. Az egylépéses állapotátmenet-valószínűség legyen:

p_ij = 1/m_i, ha i-ről mutat link j-re, vagy 0 ha nem mutat link

Egy oldal fontosságát az mutatja, hogy a Markov-lánc mekkora valószínűséggel tartózkodik az oldalnak megfelelő állapotban = a lánc határeloszlását kell meghatározni. Ezzel még van pár probléma (lehet, hogy nem lesz aperiodikus és irreducibilis), ezek ellen a következőket tesszük: A láncot egyenletes eloszlásból indítjuk, vagyis

P⁽⁰⁾ = (1/T, ..., 1/T)

eloszlásból, mivel itt mindig létezik határértéke a P⁽ⁿ⁾ eloszlásnak. A határérték:

P = PΠ

Azonban célunk nem a valószínűségek kiszámítása, hanem az oldalak rangsorolása, ahhoz pedig elég, ha a P⁽ⁿ⁾ = P^(n-1)Π iterációval a P⁽ⁿ⁾ eloszlásokat addig számoljuk, amíg a kiszámolt sorrend már nem változik.

A Pagerank algoritmus finomabb változata: Π állapotátmenet-mátrix helyett Π' = εU + (1-ε)Π mátrixot használjuk (0 < ε < 1, U mátrix minden eleme 1/T). Ez azt jelenti, hogy a fontosságok egy részét minden oldaltól beszedjük, és szétosztjuk a többi oldal között. ε annak a valószínűsége, hogy nem az aktuális, hanem véletlenszerűen valamely másik oldalról lépünk tovább. Ekkor érvényes lesz az aperiodikusság és az irreducibilitás is.

-- GK - 2006.12.19.