PageRank

Matematikai PageRank példa hálózatra, az értékrangsort százalékban kifejezve

A PageRank az informatikában egy olyan algoritmus, amely hiperlinkekkel összekötött dokumentumokhoz számokat rendel azoknak a hiperlink-hálózatban betöltött szerepe alapján. (Ezt a számot szintén PageRanknek nevezik.) A PageRank a Google internetes keresőmotor legfontosabb eleme. Larry Page és Sergey Brin (a Google alapítói) fejlesztették ki 1998-ban a Stanford Egyetemen.

A Google arra a feltételezésre épít, hogy a weboldalak készítői általában azokra az oldalakra linkelnek a saját lapjukról, amiket jónak tartanak, vagyis minden hiperlink felfogható egy-egy szavazatként a céloldalra. Minél több szavazatot kap egy oldal, annál fontosabb, de azt is figyelembe kell venni, hogy a szavazatot leadó oldal mennyire fontos. (Ez egy rekurzív definíció: az a fontos oldal, amire fontos oldalak mutatnak.) A PageRank a fontosság számszerűsítése.

A „PageRank” szó a Google bejegyzett védjegye. Az eljárást az USA-ban szabadalom védi.

A PageRank definíciója

Szavazás

A fenti alapötlet szerint kezdetben minden oldalnak egy egységnyi szavazata van, amit egyenlően szétoszt azok között az oldalak között, amikre hivatkozik, és a más oldalaktól kapott szavazatokat is ugyanígy továbbosztja. Egy oldal PageRankje megegyezik a kapott szavazatok számával (ami nem feltétlenül egész szám). Ahhoz, hogy ez az eljárás jól definiált legyen, be kell vezetni egy d csillapító tényezőt (damping factor – részletes kifejtése a következő részben): az oldalak a szavazatukból csak d részt osztanak tovább, (1-d)-t pedig megtartanak. (A mástól kapott szavazatokat teljesen továbbosztják.) Így a PageRankre a következő képlet adódik:

${\rm {PageRank}}(i)=(1-d)+d\sum _{j\in M(i)}{\frac {{\rm {PageRank}}(j)}{L(j)}}$

ahol M(i) azoknak az oldalaknak a halmaza, amik tartalmaznak linket az i. oldalra, L(j) pedig a j. oldalról kimenő linkek száma.

Normális esetben (ha kizártuk a lógó linkeket), ha a vizsgált hálózat N oldalból áll, akkor az egyes oldalak PageRankjeinek összege N lesz. Így a PageRank szavazás helyett úgy is elképzelhető, mint a kezdetben a weblapok között egyenletesen elosztott fontosság átcsoportosítása.

Sztochasztikus szörföző

A PageRanket úgy is felfoghatjuk, mint annak a valószínűségét, hogy odatalálunk az oldalra. A valószínűséget a sztochasztikus szörfözővel modellezzük, aki a weben bolyong, és minden lépésben véletlenszerűen, egyenletes eloszlás szerint kiválaszt egyet az oldalon található linkek közül, és azon halad tovább. (Más szóval véletlen bolyongást végez a hiperlinkek alkotta irányított gráfon.) Hogy ne essen csapdába valamelyik olyan részgráfban, amiből nem vezet kifelé link, a modellt kiegészítjük egy további elemmel: a szörföző minden lépésben 1-d valószínűséggel elunja magát, és egy (egyenletes eloszlás szerint) véletlenszerűen választott weblapra ugrik. Így, ha az n.-ik lépésben az egyes oldalakon tartózkodás esélyét a $p_{1}^{n},p_{2}^{n},...p_{N}^{n}$ számok adják meg, akkor a következő lépés utáni valószínűségeket a

$p_{i}^{n+1}={\frac {1-d}{N}}+d\sum _{j\in M(i)}{\frac {p_{j}^{n}}{L(j)}}$

képlettel kapjuk.

Az egyes lépésekben felvett pozíciók mint valószínűségi változók sorozata egy irreducibilis és aperiodikus Markov-láncot alkot, tehát létezik határeloszlása. (Ehhez szükséges a csillapító tényező: ha a gráf nem lenne erősen összefüggő – márpedig egy véletlen gráf 1 valószínűséggel nem az –, akkor a lánc reducibilis lenne.) Az oldal PageRankjét a határeloszlásban hozzá tartozó valószínűségként definiáljuk. Ez a következő rekurzív képletet adja a PageRankre:

${\rm {PageRank}}(i)={\frac {1-d}{N}}+d\sum _{j\in M(i)}{\frac {{\rm {PageRank}}(j)}{L(j)}}$

Ez nem azonos a szavazásos képlettel: az 1-d tényező itt le van osztva az összes oldal számával, tehát az így definiált PageRank az előzőnek éppen N-edrésze. Brin és Page eredetileg a sztochasztikus szörföző modelljéből vezette le a PageRank képletét, de eltévesztették a képletet, és az N nélküli változatot publikálták. Bár a későbbi cikkekben kijavították, mégis a „hibás” változat terjedt el, mert a gyakorlatban könnyebben számítható: N-t nehéz meghatározni, mert a kereső a folyamatosan változó világhálónak egyszerre mindig csak egy kis részét látja.

A sztochasztikus szörföző modellel definiált PageRank tehát egy valószínűségi eloszlás lesz: egy oldal PageRankje annak a valószínűsége, hogy nagyon sok véletlenszerű kattintás (és ugrás) után éppen arra az oldalra érkezünk. (A PageRank reciproka az oldal várható visszatérési ideje, azaz annak a várható értéke, hogy az oldalról elindulva hány lépés múlva érünk vissza oda.)

Lógó linkek

A lógó link (dangling link) olyan hivatkozás, ami egy zsákutcára mutat: egy olyan dokumentumra, ami egyáltalán nem tartalmaz linket. (Ilyenek gyakran előfordulnak, egyrészt mert a Google a HTML-en kívül számos más fájlformátumot is ismer, és ezek a formátumok általában nem tartalmaznak linkeket; másrészt mert a web feldolgozását valós időben végzi, és a még le nem töltött vagy fel nem dolgozott oldalakat üresnek látja.) Ezek a linkek gondot okoznak a PageRank számításakor, mert ha a sehova nem vezető oldalaknak is adunk PageRanket, akkor a rendszerben levő összes szavazat kevesebb lesz az oldalak számánál. A '98-as cikk szerint a Google a PageRank-számítás idejére átmenetileg kitörli ezeket a linkeket; hogy ez pontosan hogy történik, az nem derül ki a szövegből.

PageRank a GoogleBarban

A GoogleBar által használt, 10-es skálájú értékelést gyakran összekeverik a PageRankkel. A GoogleBar által mutatott érték jelentése valójában nem ismeretes – sokak szerint a PageRanknek a 0–10 intervallumra logaritmikusan átskálázott és kerekített értékét mutatja. (Ugyanez érvényes a Google Directory által mutatott értékekre is, csak ott 0–7-ig van a skála.)

A GoogleBar néha olyan oldalakra is ad eredményt, amik nem szerepelnek a Google indexében. Az ilyen eredmények valószínűleg a közeli oldalak PageRankjeire alapozott találgatások.

A PageRank manipulálása

A PageRank eredményeket lényegesen nehezebb manipulálni, mint a hagyományos, vektortér modellen alapuló módszereket, de nem lehetetlen. Egy bevett módszer a „comment spam”, linkek elhelyezése bárki által írható oldalakon, például vendégkönyvekben, blogokban vagy wikikben. Egy-egy ilyen link csak elenyésző mértékben növeli meg a céloldal PageRankjét, de nagy mennyiségben alkalmazva már jelentős növekedést lehet elérni. A Google a közelmúltban egy új HTML attribútumot (rel="nofollow") javasolt a „comment spam” elleni védekezésre.

A másik jellemző trükk a linkfarmok használata: olyan webszájtok készítése, ahol nagyszámú „szolga” oldal van, amelyek egyetlen haszna az, hogy a kezdetben kapott szavazatukat átadják a főoldalnak. A Google a PageRank érték 0-ra csökkentésével „bünteti” azokat a linkfarmokat, amikről tudomást szerez. Vélhetően számos más módosítást is alkalmaz, de ezeket igyekszik titokban tartani.

Személyre szabás

A 98-as cikk foglalkozik a PageRank személyre szabásának lehetőségével. A módosított változatban a sztochasztikus szörföző továbbra is egyforma valószínűséggel választ a linkek közül, de ha elunja magát, egyes oldalakra nagyobb valószínűséggel ugrik, mint másokra. Ekkor a kedvezményezett oldalak és a közelükben lévők magasabb PageRank értékeket kapnak. Egyes vélemények szerint a Google a Yahoo és az ODP oldalainál alkalmazza ezt az eljárást. A személyre szabás egy másik felhasználási módja, hogy az eloszlás nem az oldalak, hanem a domének szintjén egyenletes – ez megnövelné a linkfarmok létrehozásának költségét, mert egy doménen belül újabb oldalakat létrehozni nem kerül pénzbe, újabb doméneket szerezni viszont igen.

A valódi, felhasználónkénti személyre szabás ezzel a módszerrel a túl nagy számítási kapacitás miatt nem kivitelezhető, viszont egyes vélemények szerint a Google felhasználja a PageRank becsapásával kísérletezők „megbüntetésére”. (A SearchKing keresőoptimalizáló vállalat be is perelte egy ilyen eset miatt a Google-t, de elvesztette a pert.)

Források

• The PageRank Citation Ranking: Bringing Order to the Web – Brin és Page eredeti publikációja a PageRankről
• The Anatomy of a Large-Scale Hypertextual Web Search Engine – Brin és Page publikációja a Google-ról
• The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank (PDF)
• Deeper Inside PageRank
• Google PageRank – A Survey
• PageRank Uncovered Archiválva 2005. szeptember 15-i dátummal a Wayback Machine-ben (PDF)

További információk

• alt.internet.search-engines FAQ
• PageRank vizualizáció

Kapcsolódó szócikkek

• Google
• Weboldalak magas PageRankkel
• vektortér modell
• információkeresés (information retrieval)
• keresőoptimalizálás (Search Engine Optimalization, SEO)
• keress!

Hasonló algoritmusok

• HITS
• SALSA