PageRank
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fb/PageRanks-Example.svg/300px-PageRanks-Example.svg.png)
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.[1]
A PageRank definíciója[szerkesztés]
Szavazás[szerkeszté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:
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ő[szerkesztés]
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 számok adják meg, akkor a következő lépés utáni valószínűségeket a
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:
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[szerkesztés]
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,[2] é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[szerkesztés]
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[3] á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[szerkesztés]
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[szerkeszté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.)
Jegyzetek[szerkesztés]
- ↑ 6 285 999. számú szabadalom[halott link]
- ↑ A Google által indexelhető fájltípusok (magyar nyelven). Google Webmestereszközök Súgó. (Hozzáférés: 2015. április 5.)
- ↑ Archivált másolat. [2011. január 20-i dátummal az eredetiből archiválva]. (Hozzáférés: 2005. május 29.)
Források[szerkesztés]
- 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[szerkesztés]
Kapcsolódó szócikkek[szerkesztés]
- Weboldalak magas PageRankkel
- vektortér modell
- információkeresés (information retrieval)
- keresőoptimalizálás (Search Engine Optimalization, SEO)
- keress!