Der
Algorithmus
Gewichtung im World Wide Web
- Die Funktionsweise von großen Hypertext Suchmaschinen -
Der nachfolgende Text basiert auf einer Facharbeit, die ich 2007 im Fach Informatik angefertigt habe und wurde in Inhalt und Layout nur geringfügig geändert und erweitert.
Inhaltsverzeichnis
Um das Auffinden von relevanten Seiten zu vereinfachen und weniger zeitintensiv zu gestallten, wurden Suchmaschinen entwickelt, die aus den abermilliarden von Webseiten diejenigen heraussuchen sollen, die die gesuchten Informationen beinhalten. Doch wie erreichen die modernen Suchmaschinen dieses Ziel?
Eine sehr populäre Methode ist der so genannte PageRank Algorithmus, der von der Suchmaschine Google verwendet wird.
Nachfolgend soll nun die Funktionsweise sowie die Vor- und Nachteile dieses Verfahrens erläutert werden.
Verwendet wird der Algorithmus von der Internetsuchmaschine Google, die von Sergey Brin und Lawrence Page am 7. September 1998 gegründet wurde.
Der Algorithmus revolutionierte den Markt der Internetsuchmaschinen und machte Google zum Marktführer mit einem Jahresumsatz von heute mehr als 10,6 Milliarden US-Dollar [3].
Das Revolutionäre am PageRank-Algorithmus war, dass er nicht die leicht zu manipulierende Häufigkeit der Suchbegriffe innerhalb einer Webseite als Bewertungskriterium heranzog, sondern einen völlig neuen Weg ging.
Bewertet werden die Seiten anhand der Anzahl an Drittseiten, welche auf die gesuchte Seite verweisen sowie wiederum die Gewichtung dieser Seiten.
Die Google Incorporation gewährt heute keinen genauen Einblick mehr in den Algorithmus, der zur Zeit zur Berechnung verwendet wird, es wird aber vermutet, dass der ursprüngliche PageRank-Algorithmus im Laufe der Zeit angepasst wurde, um auf die erheblichen Veränderungen des World Wide Web zu reagieren.
Die naheliegenste und damals wie heute weit verbreitete Methode zur Relevanzbewertung einer Webseite ist die Messung der Häufigkeit des Vorkommens eines Suchbegriffes. Wird ein bestimmter Begriff angefragt, so liefert vermutlich die Seite die gesuchten Informationen, die diesen Begriff am häufigsten verwendet.
Ein solches Suchsystem ist jedoch recht anfällig gegenüber Manipulation. Ist ein Seitenbetreiber daran interessiert, dass seine Internetpräsenz im Zusammenhang mit einem bestimmten Begriff ein gutes Suchergebnis erzielt, so kann er dies erreichen, indem er besagten Begriff häufig auf seinen Seiten verwendet. Dies muss nicht zwingend für den späteren Betrachter offensichtlich geschehen, sondern kann durch verschiedene simple Methoden verschleiert werden.
Aufgrund dieser leichten Manipulierbarkeit schuf man das System der Link-Gewichtung. Eine Seite erhielt dann ein gutes Suchergebnis, wenn sie den gesuchten Begriff enthielt und von vielen anderen Seiten auf sie verwiesen wurde.
Doch auch dieses System stellte sich als leicht manipulierbar heraus. Die Seitenbetreiber erstellten so genannte Doorway Pages oder zu Deutsch Brückenseiten, welche - gespickt mit dem gewünschten Suchbegriff – keine andere Funktion hatten, als auf die eigentliche Seite zu verweisen. Durch das massenhafte Anlegen solcher Brückenseiten manipulierten die Seitenbetreiber die Link-Gewichtung ihrer Seiten und verfälschten die Suchergebnisse.
Der Ansatz von Sergey Brin und Lawrence Page zielte nun darauf ab, dass nicht jeder Link auf eine Internetseite gleich gewichtet werden sollte, sondern wiederum die Link-Gewichtung der ausgehenden Seite für den Wert eines Verweises maßgebend sein sollte. Demnach steigt die Gewichtung einer Seite – der so genannte PageRank – stärker an, wenn eine populäre Seite mit einem ihrerseits hohen PageRank auf diese verweist, als wenn der Verweis von einer unpopulären Seite mit niedrigem PageRank ausgeht.
Existiert auf der Startseite des Benutzers nur ein einzelner Verweis, so beträgt die Wahrscheinlichkeit, dass der Surfer diesen Link verwendet annähernd 100%. Annähernd deswegen, weil er auch einfach den Browser schließen und keine weitere Seite ansurfen oder manuell die Adresse einer gewünschten Seite eingeben kann. Existieren auf der Startseite jedoch Verweise auf mehrere Seiten, so sinkt die Wahrscheinlichkeit für jeden dieser Links entsprechend ab. Der PageRank Algorithmus muss demnach in die Gewichtung eines Verweises die Anzahl an Links auf der verweisenden Seite mit berücksichtigen.
Weiterhin verfolgen Page und Brin die Annahme, dass eine gewisse Wahrscheinlichkeit besteht, dass der Zufallssurfer das Betrachten einer Seite unterbricht und eine neue Seite aufruft ohne einem Link zu folgen. Die Wahrscheinlichkeit, dass ein Benutzer einem bestimmten Link auf einer Seite folgt ist im Zuge dessen nicht nur abhängig von der Gesamtanzahl an Links auf dieser Seite, sondern auch von der Wahrscheinlichkeit, mit der der Zufallssurfer keinem Link folgt. Dies führt auch dazu, dass die Berechnung des PageRank nicht durch Seiten, die keinerlei ausgehende Links enthalten verfälscht wird.
Setzt man diese Überlegungen in eine Gleichung um, so erhält man den von Page und Brin entwickelten Algorithmus:
Der PageRank PRA der Seite A berechnet sich also aus der Wahrscheinlichkeit, mit der ein Benutzer auf dieser startet bzw. diese manuell aufruft mit 1-d. Zu dieser wird die Wahrscheinlichkeit addiert, mit der er durch einen Link auf die Seite A gelangt.
Diese Wahrscheinlichkeit ist die Summe der Wahrscheinlichkeiten, dass der Benutzer einem Link auf den Seiten i folgt multipliziert mit dem Faktor d.
Der Faktor d wird als Dämpfungsfaktor bezeichnet und gibt durch einen Wert 0 <= d <= 1 die Wahrscheinlichkeit an, mit der der Benutzer keinem Link folgt, sondern eine Seite manuell aufruft. Die Wahrscheinlichkeit, mit der der Benutzer keinem Link folgt wird direkt mit dem PageRank der Seiten i verrechnet. Somit fliest in den PageRank der Seite A der Quotient aus dem PageRank jeder Seite i und der Anzahl an Links auf den Seiten i ein.
Zusammenfassend bedeutet dies:
In dem Beispiel besteht das Internet aus nur drei Seiten. Die Linkstruktur wird durch die Pfeile symbolisiert, sodass sich auf Seite A ein Link zu Seite B befindet. Seite B verlinkt sowohl Seite A als auch Seite C. Auf Seite C befindet sich ein Verweis auf Seite A.
Setzt man den Dämpfungsfaktor wie von Brin und Page für den Normalfall angegeben auf 0,85 ergeben sich folgende Gleichungen.
PRA = 1-0,85 + 0,85 * (PRB/2 + PRC)
PRB = 1-0,85 + 0,85 * PRA
PRC = 1-0,85 + 0,85 * PRB/2
Es zeigt sich, dass die Berechnung des PageRanks rekursiv ablaufen muss. Das Ergebnis für dieses einfache Beispiel wäre:
PRA = 1,192198979
PRB = 1,163369132
PRC = 0,644431881
Addiert man die PageRanks, so erhält man den Wert drei, also die Gesamtanzahl der Seiten dieses Beispiels. Nach dem Zufallssurfermodell lässt sich dadurch ableiten, dass Seite A zu 40%, Seite B zu 39% und Seite C zu 21% besucht wird.
Obwohl also auf Seite B und Seite C gleich viele Links verweisen, ist der PageRank und damit die Wahrscheinlichkeit eines Aufrufes der Seite B beinahe doppelt so hoch wie der der Seite C. Dies liegt daran, dass Seite A durch die höhere Anzahl an auf sie zeigende Verweise gewichtiger ist – einen höheren PageRank besitzt – und somit ihrem Verweis auf Seite B eine höhere Gewichtung zukommt.
Zur besseren Darstellung wird für die Seite X ein PageRank von 10 und für die Seiten A, B, C und D jeweils ein PageRank von 1 angenommen. Damit ergeben sich bei einem Dämpfungsfaktor von 0,85 die entsprechenden PageRank Werte:
PRA = 1 - 0,85 + 0,85 * (PRD + PRX) = 18,78265929
PRB = 1 - 0,85 + 0,85 * PRA = 16,1152604
PRC = 1 - 0,85 + 0,85 * PRB = 13,84797134
PRD = 1 - 0,85 + 0,85 * PRC = 11,92077564
Der PageRank der Seite A wird also um ca. 18 Punkte angehoben, obwohl lediglich eine Anhebung um d * PRX / CX also 8,5 zu erwarten gewesen wäre. Doch diese Erhöhung setzt sich auf die Seiten B, C und D fort, sodass die Seite D ebenfalls einen um ca. 11 Punkte angehobenen PageRank erhält. Da diese wiederum auf Seite A verlinkt, wird der PageRank der Seite A erneut angehoben. Alle Seiten A, B, C und D profitieren somit mehrfach von dem eingehenden Verweis von Seite X.
Wie lässt sich die Anhebung des PageRank also nun berechnen?
Bleibt man bei dem vorliegenden Beispiel, ändert aber den Dämpfungsfaktor auf 0,425 ab, so ändern sich die PageRanks der Seiten entsprechend:
PRA = 1 - 0,425 + 0,425 * (PRD + PRX) = 5,393334246
PRB = 1 - 0,425 + 0,425 * PRA = 2,867167055
PRC = 1 - 0,425 + 0,425 * PRB = 1,793545998
PRD = 1 - 0,425 + 0,425 * PRC = 1,337257049
Der addierte PageRank aller Seiten des ersten Beispiels ergibt 60, der des zweiten 11. Bei einem angenommenen Startwert von einem jeweiligen PageRank von 1 wird der gesamt PageRank im ersten Beispiel demnach um 56 Punkte angehoben, im zweiten Beispiel nur noch um 7 Punkte. Gleichzeitig ist der PageRank der Seite A im ersten Beispiel nur ca. 1,5-mal so hoch wie der der Seite D. Im zweiten Beispiel jedoch 4-mal so hoch. Es zeigt sich also, dass der Dämpfungsfaktor sowohl die Gewichtung eines eingehenden Links beeinflusst, als auch die Verteilung dieses Effekts auf die nachfolgenden Seiten reguliert.
Demnach kann der Einfluss einer Seite X auf den PageRank der in sich geschlossenen Seiten A, B, C und D mit ΔPR = (d / (1-d)) * (PRX / CX) angegeben werden.
Analog dazu lässt sich der Verlust an PageRank Punkten für ein System an Webseiten ermitteln, welches einen Link auf ein anderes System enthält.
Wäre die Seite X aus obigem Beispiel also ihrerseits ein Teil des Webseiten Systems X, Y und Z, so würde dieses System an PageRank in der Höhe von ΔPR verlieren.
Zurückgeführt auf das Modell des Zufallssurfers lässt sich dieses Phänomen damit erklären, dass der Zufallssurfer das System X, Y, Z durch das Vorhandensein eines Verweises auf die Seite A mit einer höheren Wahrscheinlichkeit verlässt, als wenn das System keine externen Links enthalten würde und somit in sich geschlossen wäre.
Betrachtet man den PageRank eines Systems wie in Abbildung drei dargestellt, so zeigt sich, dass Seiten ohne ausgehende Verweise den PageRank des gesamten Systems negativ beeinflussen.
PRA = 0,15 + 0,85 * PRB = 0,43444227
PRB = 0,15 + 0,85 * (PRA / CA) = 0,334637964
PRC = 0,15 + 0,85 * (PRA / CA) = 0,334637964
Der tatsächliche PageRank des betrachteten Systems wäre demnach 2,7-mal kleiner als erwartet. Um diesem Effekt entgegen zu wirken, werden nach Lawrence Page und Sergey Brin Verweise auf Seiten ohne ausgehende Links – die so genannten Dangling Links (engl. „baumelnde Verweise“) – für die Berechnung des PageRanks zunächst ignoriert. Da durch das Ignorieren eines Dangling Links erneut ein solcher entstehen könnte, sind mehrere iterative Prüfvorgänge nötig, um alle störenden Verweise zu entfernen. Anschließend werden nun die PageRanks der verbleibenden Seiten ermittelt und im Anschluss erneut rekursiv die entsprechenden Werte für die zuvor ignorierten Seiten bestimmt. Durch dieses Verfahren ergeben sich für obiges Beispiel angepasste Werte.
PRA = 0,15 + 0,85 * PRB = 1
PRB = 0,15 + 0,85 * PRA = 1
Demnach beträgt der PageRank der Seite C
PRC = 0,15 + 0,85 * (PRA / CA) = 0,575
Es zeigt sich, dass der addierte PageRank des Systems immer noch um 0,425 kleiner ist als eigentlich erwartet, jedoch wurde der Effekt des Dangling Links von Seite A auf Seite C erheblich minimiert und hat nun keinerlei Einfluss mehr auf den PageRank der Seiten A und B.
Bei dem verwendeten Verfahren wird einer jeden Seite zunächst ein fiktiver PageRank zugewiesen. Anschließend wird basierend auf diesem Startwert der PageRank einer jeden Seite berechnet. Das Ergebnis stellt einen Näherungswert für den tatsächlichen PageRank der Seite dar. Wird der Vorgang nun basierend auf dem jeweils vorhergehenden Ergebnis wiederholt, so nähert sich der errechnete PageRank immer weiter dem tatsächlichen an.
Es ist offensichtlich, dass je näher der fiktive Startwert am tatsächlichen PageRank Wert einer Seite liegt, desto weniger Wiederholungen nötig sind um eine ausreichende Genauigkeit zu erzielen. Es empfiehlt sich also bei einer erneuten Berechnung des PageRanks einer Seite deren „alten“ Wert aus der letzten Berechnung zu verwenden, um den Rechenaufwand weiter zu reduzieren.
Nach Angabe von Brin und Page ist eine ausreichend hohe Genauigkeit gegeben, wenn die Summe der Abweichungen pro Iteration weniger als 100 beträgt. Nach ihren Angaben reichen für eine Menge von rund 322 Mio. Webseiten 52 Iterationen aus, um einen akzeptablen Näherungswert für jeden PageRank zu bestimmen.
Doch wie lässt sich ein solcher Begriff mit dem Random Surfer Modell hinter dem PageRank Algorithmus vereinbaren? Nun, zunächst einmal umfasst die Suchmaschinenoptimierung weitaus mehr Gebiete als nur den PageRank, aber nichts-destotrotz würde eine mögliche Manipulation die Vorteile des PageRank Verfahrens zunichte machen.
Betrachtet man jedoch den Schneeballeffekt des PageRank und das Verhalten dieses bei Erstellung eines einzigen externen Verweises (vgl. 2.3), so zeigt sich, dass in jedem Fall das verlinkende System als Ganzes an PageRank verlieren wird.
Hinzu kommt, dass der Zuwachs an PageRank, den die verlinkte Seite erfährt, auf alle nachfolgenden Seiten verteilt wird. Besteht eine Webseite also aus vielen Unterseiten, so minimiert sich der Effekt für jede einzelne.
In den meisten Fällen profitiert somit nur eine der beiden Seiten von einer derartigen Verabredung, wobei zugleich der tatsächliche Nutzen für diese Seite oft sehr gering ausfällt.
Ausgehend von den Überlegungen zum Linktausch muss in diesen Fällen also bedacht werden, dass beide Betreiber den Kosten/Nutzen Faktor eines solchen Betruges berücksichtigen sollten. Während der Betreiber der verlinkenden Seite abwägen muss, ob ihm die gebotene Summe den Verlust an PageRank wert ist, so muss der Betreiber der verlinkten Seite abschätzen, ob eine solche Investition für die ggf. minimale Änderung des PageRanks seiner Seite lohnenswert ist.
Hinzukommt, dass sich Google das Recht an manuellen Änderungen einzelner PageRank Werte vorbehält. Sollten also Betrugsversuche bekannt werden, so drohen den entsprechenden Seiten erhebliche Abzüge beim PageRank.
Es gilt beinahe der Grundsatz, wer wer bei Google nicht gefunden werden kann, der existiert nicht. Gerade für Unternehmen spielt die Auffindbarkeit ihrer Webseiten bei der Schaffung neuer und der Pflege alter Geschäftsbeziehungen eine große Rolle. Doch keine Webseite hat das Recht auf einen hohen PageRank, ja noch nicht einmal auf die Korrekte Berechnung nach den Regeln des Algorithmuses.
Google besitzt hier eine extreme Machtstellung, und verfügt somit grundsätzlich über die Möglichkeit aufkommende Konkurrenz bereits im Keim zu ersticken. Ob und in wie weit manuelle Manipulationen am PageRank einzelner Seiten tatsächlich auf Googles urgeigenes, wirtschaftliches Interesse zurück zuführen sind bleibt aber vorerst reine Spekulation.
[2] Sergey Brin und Lawrence Page: The Anatomy of a Large Scale Hypertextual Web Search Engine, Computer Science Department, Stanford University, 1998
[3] heise online: Google legt weiter kräftig zu, 2007
[4] heise online: Google in Deutschland über 90 Prozent, 2006
Inhaltsverzeichnis
1. Einleitung
1.1 Einführung
In den letzten Jahren ist die Anzahl an Webseiten im World Wide Web extrem angestiegen. Sich in dieser Flut an Informationen zurecht zu finden, fällt selbst versierten Anwendern schwer und oft ist es nicht einfach, nützliche von unnützlichen Informationen zu unterscheiden.Um das Auffinden von relevanten Seiten zu vereinfachen und weniger zeitintensiv zu gestallten, wurden Suchmaschinen entwickelt, die aus den abermilliarden von Webseiten diejenigen heraussuchen sollen, die die gesuchten Informationen beinhalten. Doch wie erreichen die modernen Suchmaschinen dieses Ziel?
Eine sehr populäre Methode ist der so genannte PageRank Algorithmus, der von der Suchmaschine Google verwendet wird.
Nachfolgend soll nun die Funktionsweise sowie die Vor- und Nachteile dieses Verfahrens erläutert werden.
1.2 Begriffserklärung
Der Begriff PageRank stammt aus dem Englischen und bedeutet so viel wie Seitenrang. In der Informations-Technologie wird mit diesem Begriff ein Algorithmus – d.h. eine Formel bzw. eine Handlungsvorschrift – zur Berechnung der Gewichtung einer Internetseite bezeichnet.1.3 Geschichte des Algorithmus
Der PageRank-Algorithmus wurde Ende der 90er Jahre an der Stanford Universität von Sergey Brin und Lawrence Page entwickelt. Sie veröffentlichten ihr Ergebnis am 29. Januar 1998 in “The PageRank Citation Ranking: Bringing Order to the Web” [1] sowie in “The Anatomy of Large-Scale Hypertextual Web Search Engine” [2]Verwendet wird der Algorithmus von der Internetsuchmaschine Google, die von Sergey Brin und Lawrence Page am 7. September 1998 gegründet wurde.
Der Algorithmus revolutionierte den Markt der Internetsuchmaschinen und machte Google zum Marktführer mit einem Jahresumsatz von heute mehr als 10,6 Milliarden US-Dollar [3].
Das Revolutionäre am PageRank-Algorithmus war, dass er nicht die leicht zu manipulierende Häufigkeit der Suchbegriffe innerhalb einer Webseite als Bewertungskriterium heranzog, sondern einen völlig neuen Weg ging.
Bewertet werden die Seiten anhand der Anzahl an Drittseiten, welche auf die gesuchte Seite verweisen sowie wiederum die Gewichtung dieser Seiten.
Die Google Incorporation gewährt heute keinen genauen Einblick mehr in den Algorithmus, der zur Zeit zur Berechnung verwendet wird, es wird aber vermutet, dass der ursprüngliche PageRank-Algorithmus im Laufe der Zeit angepasst wurde, um auf die erheblichen Veränderungen des World Wide Web zu reagieren.
1.4 Die Entwicklung zum PageRank
Wie bereits erwähnt, hat der PageRank-Algorithmus den Suchmaschinenmarkt revolutioniert und maßgeblich zu Googles Erfolgsgeschichte beigetragen. Die Grundidee des Algorithmus ist dabei jedoch recht simpel.Die naheliegenste und damals wie heute weit verbreitete Methode zur Relevanzbewertung einer Webseite ist die Messung der Häufigkeit des Vorkommens eines Suchbegriffes. Wird ein bestimmter Begriff angefragt, so liefert vermutlich die Seite die gesuchten Informationen, die diesen Begriff am häufigsten verwendet.
Ein solches Suchsystem ist jedoch recht anfällig gegenüber Manipulation. Ist ein Seitenbetreiber daran interessiert, dass seine Internetpräsenz im Zusammenhang mit einem bestimmten Begriff ein gutes Suchergebnis erzielt, so kann er dies erreichen, indem er besagten Begriff häufig auf seinen Seiten verwendet. Dies muss nicht zwingend für den späteren Betrachter offensichtlich geschehen, sondern kann durch verschiedene simple Methoden verschleiert werden.
Aufgrund dieser leichten Manipulierbarkeit schuf man das System der Link-Gewichtung. Eine Seite erhielt dann ein gutes Suchergebnis, wenn sie den gesuchten Begriff enthielt und von vielen anderen Seiten auf sie verwiesen wurde.
Doch auch dieses System stellte sich als leicht manipulierbar heraus. Die Seitenbetreiber erstellten so genannte Doorway Pages oder zu Deutsch Brückenseiten, welche - gespickt mit dem gewünschten Suchbegriff – keine andere Funktion hatten, als auf die eigentliche Seite zu verweisen. Durch das massenhafte Anlegen solcher Brückenseiten manipulierten die Seitenbetreiber die Link-Gewichtung ihrer Seiten und verfälschten die Suchergebnisse.
Der Ansatz von Sergey Brin und Lawrence Page zielte nun darauf ab, dass nicht jeder Link auf eine Internetseite gleich gewichtet werden sollte, sondern wiederum die Link-Gewichtung der ausgehenden Seite für den Wert eines Verweises maßgebend sein sollte. Demnach steigt die Gewichtung einer Seite – der so genannte PageRank – stärker an, wenn eine populäre Seite mit einem ihrerseits hohen PageRank auf diese verweist, als wenn der Verweis von einer unpopulären Seite mit niedrigem PageRank ausgeht.
2. Der Algorithmus
2.1 Das Modell des Zufallssurfers
Im Sinne von Lawrence Page und Sergey Brin stellt der PageRank Algorithmus eine Simulation dar. Die beiden gehen davon aus, dass ein Benutzer, der so genannte Random Surfer, auf einer beliebigen Seite des Internets startet und diese eine Zeit lang betrachtet. Anschließend folgt er einem beliebigen Link auf der Seite, ohne dass für ihn der Inhalt der Seite eine Rolle spielt.Existiert auf der Startseite des Benutzers nur ein einzelner Verweis, so beträgt die Wahrscheinlichkeit, dass der Surfer diesen Link verwendet annähernd 100%. Annähernd deswegen, weil er auch einfach den Browser schließen und keine weitere Seite ansurfen oder manuell die Adresse einer gewünschten Seite eingeben kann. Existieren auf der Startseite jedoch Verweise auf mehrere Seiten, so sinkt die Wahrscheinlichkeit für jeden dieser Links entsprechend ab. Der PageRank Algorithmus muss demnach in die Gewichtung eines Verweises die Anzahl an Links auf der verweisenden Seite mit berücksichtigen.
Weiterhin verfolgen Page und Brin die Annahme, dass eine gewisse Wahrscheinlichkeit besteht, dass der Zufallssurfer das Betrachten einer Seite unterbricht und eine neue Seite aufruft ohne einem Link zu folgen. Die Wahrscheinlichkeit, dass ein Benutzer einem bestimmten Link auf einer Seite folgt ist im Zuge dessen nicht nur abhängig von der Gesamtanzahl an Links auf dieser Seite, sondern auch von der Wahrscheinlichkeit, mit der der Zufallssurfer keinem Link folgt. Dies führt auch dazu, dass die Berechnung des PageRank nicht durch Seiten, die keinerlei ausgehende Links enthalten verfälscht wird.
Setzt man diese Überlegungen in eine Gleichung um, so erhält man den von Page und Brin entwickelten Algorithmus:
Der PageRank PRA der Seite A berechnet sich also aus der Wahrscheinlichkeit, mit der ein Benutzer auf dieser startet bzw. diese manuell aufruft mit 1-d. Zu dieser wird die Wahrscheinlichkeit addiert, mit der er durch einen Link auf die Seite A gelangt.
Diese Wahrscheinlichkeit ist die Summe der Wahrscheinlichkeiten, dass der Benutzer einem Link auf den Seiten i folgt multipliziert mit dem Faktor d.
Der Faktor d wird als Dämpfungsfaktor bezeichnet und gibt durch einen Wert 0 <= d <= 1 die Wahrscheinlichkeit an, mit der der Benutzer keinem Link folgt, sondern eine Seite manuell aufruft. Die Wahrscheinlichkeit, mit der der Benutzer keinem Link folgt wird direkt mit dem PageRank der Seiten i verrechnet. Somit fliest in den PageRank der Seite A der Quotient aus dem PageRank jeder Seite i und der Anzahl an Links auf den Seiten i ein.
Zusammenfassend bedeutet dies:
| PRA | Der resultierende PageRank der Seite A |
| d | Der Dämpfungsfaktor, der die Wahrscheinlichkeit angibt, mit der ein Benutzer einem Link folgt |
| i | Eine Seite, die einen Verweis auf Seite A enthält |
| n | Die Anzahl an Seiten, die einen Link auf Seite A enthalten |
| PRi | Der PageRank einer Seite i, die auf Seite A verweist |
| Ci | Die Anzahl an Links, die sich auf einer Seite i befinden |
| 1-d | Das Gegenstück zum Dämpfungsfaktor und somit die Wahrscheinlichkeit, dass ein Benutzer die Seite A aufruft ohne einem Link gefolgt zu sein. |
2.2 Ein erstes Beispiel
Betrachtet man die Formel an einem kleinen Beispiel mit nur drei Seiten, so wird die Funktionsweise verdeutlicht.
In dem Beispiel besteht das Internet aus nur drei Seiten. Die Linkstruktur wird durch die Pfeile symbolisiert, sodass sich auf Seite A ein Link zu Seite B befindet. Seite B verlinkt sowohl Seite A als auch Seite C. Auf Seite C befindet sich ein Verweis auf Seite A.
Setzt man den Dämpfungsfaktor wie von Brin und Page für den Normalfall angegeben auf 0,85 ergeben sich folgende Gleichungen.
PRA = 1-0,85 + 0,85 * (PRB/2 + PRC)
PRB = 1-0,85 + 0,85 * PRA
PRC = 1-0,85 + 0,85 * PRB/2
Es zeigt sich, dass die Berechnung des PageRanks rekursiv ablaufen muss. Das Ergebnis für dieses einfache Beispiel wäre:
PRA = 1,192198979
PRB = 1,163369132
PRC = 0,644431881
Addiert man die PageRanks, so erhält man den Wert drei, also die Gesamtanzahl der Seiten dieses Beispiels. Nach dem Zufallssurfermodell lässt sich dadurch ableiten, dass Seite A zu 40%, Seite B zu 39% und Seite C zu 21% besucht wird.
Obwohl also auf Seite B und Seite C gleich viele Links verweisen, ist der PageRank und damit die Wahrscheinlichkeit eines Aufrufes der Seite B beinahe doppelt so hoch wie der der Seite C. Dies liegt daran, dass Seite A durch die höhere Anzahl an auf sie zeigende Verweise gewichtiger ist – einen höheren PageRank besitzt – und somit ihrem Verweis auf Seite B eine höhere Gewichtung zukommt.
2.3 Der Schneeballeffekt und der Einfluss des Dämpfungsfaktors
Ausgehend von diesem Beispiel scheint es, dass ein auf Seite A zeigender Verweis auf einer Seite B den PageRank der Seite A um d * PRB / CB erhöht. Bei Beobachtung des PageRank einer Seite zeigt sich aber, dass dies nicht der Fall ist. Der Effekt der Erhöhung des PageRank der Seite A setzt sich auf alle nachfolgenden Seiten fort und kommt somit der Seite A in mehrfacher Form zu Gute. Um diesen Effekt zu verdeutlichen wird erneut ein Miniaturbeispiel aus fünf Seiten betrachtet.
Zur besseren Darstellung wird für die Seite X ein PageRank von 10 und für die Seiten A, B, C und D jeweils ein PageRank von 1 angenommen. Damit ergeben sich bei einem Dämpfungsfaktor von 0,85 die entsprechenden PageRank Werte:
PRA = 1 - 0,85 + 0,85 * (PRD + PRX) = 18,78265929
PRB = 1 - 0,85 + 0,85 * PRA = 16,1152604
PRC = 1 - 0,85 + 0,85 * PRB = 13,84797134
PRD = 1 - 0,85 + 0,85 * PRC = 11,92077564
Der PageRank der Seite A wird also um ca. 18 Punkte angehoben, obwohl lediglich eine Anhebung um d * PRX / CX also 8,5 zu erwarten gewesen wäre. Doch diese Erhöhung setzt sich auf die Seiten B, C und D fort, sodass die Seite D ebenfalls einen um ca. 11 Punkte angehobenen PageRank erhält. Da diese wiederum auf Seite A verlinkt, wird der PageRank der Seite A erneut angehoben. Alle Seiten A, B, C und D profitieren somit mehrfach von dem eingehenden Verweis von Seite X.
Wie lässt sich die Anhebung des PageRank also nun berechnen?
Bleibt man bei dem vorliegenden Beispiel, ändert aber den Dämpfungsfaktor auf 0,425 ab, so ändern sich die PageRanks der Seiten entsprechend:
PRA = 1 - 0,425 + 0,425 * (PRD + PRX) = 5,393334246
PRB = 1 - 0,425 + 0,425 * PRA = 2,867167055
PRC = 1 - 0,425 + 0,425 * PRB = 1,793545998
PRD = 1 - 0,425 + 0,425 * PRC = 1,337257049
Der addierte PageRank aller Seiten des ersten Beispiels ergibt 60, der des zweiten 11. Bei einem angenommenen Startwert von einem jeweiligen PageRank von 1 wird der gesamt PageRank im ersten Beispiel demnach um 56 Punkte angehoben, im zweiten Beispiel nur noch um 7 Punkte. Gleichzeitig ist der PageRank der Seite A im ersten Beispiel nur ca. 1,5-mal so hoch wie der der Seite D. Im zweiten Beispiel jedoch 4-mal so hoch. Es zeigt sich also, dass der Dämpfungsfaktor sowohl die Gewichtung eines eingehenden Links beeinflusst, als auch die Verteilung dieses Effekts auf die nachfolgenden Seiten reguliert.
Demnach kann der Einfluss einer Seite X auf den PageRank der in sich geschlossenen Seiten A, B, C und D mit ΔPR = (d / (1-d)) * (PRX / CX) angegeben werden.
Analog dazu lässt sich der Verlust an PageRank Punkten für ein System an Webseiten ermitteln, welches einen Link auf ein anderes System enthält.
Wäre die Seite X aus obigem Beispiel also ihrerseits ein Teil des Webseiten Systems X, Y und Z, so würde dieses System an PageRank in der Höhe von ΔPR verlieren.
Zurückgeführt auf das Modell des Zufallssurfers lässt sich dieses Phänomen damit erklären, dass der Zufallssurfer das System X, Y, Z durch das Vorhandensein eines Verweises auf die Seite A mit einer höheren Wahrscheinlichkeit verlässt, als wenn das System keine externen Links enthalten würde und somit in sich geschlossen wäre.
2.4 „Baumelnde“ Verweise
Betrachtet man das Web und dessen Linkstruktur, so tauchen in relativ hoher Anzahl Seiten auf, die selber keine Verweise auf andere Seiten enthalten. Dies können sowohl normale Webseiten sein, die sich am Ende einer baumartigen Struktur befinden, als auch beispielsweise Dokumenttypen, die aufgrund ihrer spezifischen Eigenschaften keine Verweise auf andere Seiten besitzen.
Betrachtet man den PageRank eines Systems wie in Abbildung drei dargestellt, so zeigt sich, dass Seiten ohne ausgehende Verweise den PageRank des gesamten Systems negativ beeinflussen.
PRA = 0,15 + 0,85 * PRB = 0,43444227
PRB = 0,15 + 0,85 * (PRA / CA) = 0,334637964
PRC = 0,15 + 0,85 * (PRA / CA) = 0,334637964
Der tatsächliche PageRank des betrachteten Systems wäre demnach 2,7-mal kleiner als erwartet. Um diesem Effekt entgegen zu wirken, werden nach Lawrence Page und Sergey Brin Verweise auf Seiten ohne ausgehende Links – die so genannten Dangling Links (engl. „baumelnde Verweise“) – für die Berechnung des PageRanks zunächst ignoriert. Da durch das Ignorieren eines Dangling Links erneut ein solcher entstehen könnte, sind mehrere iterative Prüfvorgänge nötig, um alle störenden Verweise zu entfernen. Anschließend werden nun die PageRanks der verbleibenden Seiten ermittelt und im Anschluss erneut rekursiv die entsprechenden Werte für die zuvor ignorierten Seiten bestimmt. Durch dieses Verfahren ergeben sich für obiges Beispiel angepasste Werte.
PRA = 0,15 + 0,85 * PRB = 1
PRB = 0,15 + 0,85 * PRA = 1
Demnach beträgt der PageRank der Seite C
PRC = 0,15 + 0,85 * (PRA / CA) = 0,575
Es zeigt sich, dass der addierte PageRank des Systems immer noch um 0,425 kleiner ist als eigentlich erwartet, jedoch wurde der Effekt des Dangling Links von Seite A auf Seite C erheblich minimiert und hat nun keinerlei Einfluss mehr auf den PageRank der Seiten A und B.
2.5 Die iterative Berechnung des PageRank
Die bisher gezeigten Beispiele sind in der Anzahl ihrer Seiten stark begrenzt. Dadurch ergibt sich ein verhältnismäßig einfacher Berechnungsweg für die PageRank Werte jeder einzelnen Seite. Betrachtet man jedoch das gesamte Web, so steigt nicht nur die Anzahl an Seiten erheblich an, sondern auch die Verlinkung und somit die Abhängigkeit unter den einzelnen Seiten wird wesentlich komplexer. Die Berechnung der PageRank Werte für das gesamte Web würde demnach eine extreme Rechenleistung beanspruchen und viel Zeit benötigen. Um dies zu vermeiden wurde die Berechnung entsprechend angepasst und die Berechnung des PageRank jediglich als Approximation implementiert.Bei dem verwendeten Verfahren wird einer jeden Seite zunächst ein fiktiver PageRank zugewiesen. Anschließend wird basierend auf diesem Startwert der PageRank einer jeden Seite berechnet. Das Ergebnis stellt einen Näherungswert für den tatsächlichen PageRank der Seite dar. Wird der Vorgang nun basierend auf dem jeweils vorhergehenden Ergebnis wiederholt, so nähert sich der errechnete PageRank immer weiter dem tatsächlichen an.
Es ist offensichtlich, dass je näher der fiktive Startwert am tatsächlichen PageRank Wert einer Seite liegt, desto weniger Wiederholungen nötig sind um eine ausreichende Genauigkeit zu erzielen. Es empfiehlt sich also bei einer erneuten Berechnung des PageRanks einer Seite deren „alten“ Wert aus der letzten Berechnung zu verwenden, um den Rechenaufwand weiter zu reduzieren.
Nach Angabe von Brin und Page ist eine ausreichend hohe Genauigkeit gegeben, wenn die Summe der Abweichungen pro Iteration weniger als 100 beträgt. Nach ihren Angaben reichen für eine Menge von rund 322 Mio. Webseiten 52 Iterationen aus, um einen akzeptablen Näherungswert für jeden PageRank zu bestimmen.
3. Suchmaschinenoptimierung – Kritik Am PageRank
3.1 Das Grundproblem
Das World Wide Web hat sich in den letzten Jahren immer mehr zu einem Marktplatz entwickelt. Es geht nicht mehr einfach nur darum, Informationen bereit zu stellen und Wissen aus zu tauschen – viele Firmen benutzen das Internet um für ihre Produkte zu werben und diese zu verkaufen. Im Zuge dieser Entwicklung spielten die Positionen der eigenen Webseiten in Suchergebnissen für Marketingabteilungen eine immer größer werdende Rolle. Es wurde der Begriff der Suchmaschinenoptimierung oder kurz SEO (engl.: search engine optimization) geprägt.Doch wie lässt sich ein solcher Begriff mit dem Random Surfer Modell hinter dem PageRank Algorithmus vereinbaren? Nun, zunächst einmal umfasst die Suchmaschinenoptimierung weitaus mehr Gebiete als nur den PageRank, aber nichts-destotrotz würde eine mögliche Manipulation die Vorteile des PageRank Verfahrens zunichte machen.
3.2 Linktausch
Wurden früher in großer Anzahl Suchbegriffe auf Webseiten platziert oder eine Vielzahl an Doorway Pages erstellt, so soll heutzutage oftmals ein Linktausch für eine bessere Platzierung in den Suchergebnissen sorgen. Hierbei vereinbaren die Betreiber zweier Seiten einen Link auf die Seite des jeweils anderen zu erstellen und erhoffen sich dadurch die Steigerung ihres eigenen PageRanks.Betrachtet man jedoch den Schneeballeffekt des PageRank und das Verhalten dieses bei Erstellung eines einzigen externen Verweises (vgl. 2.3), so zeigt sich, dass in jedem Fall das verlinkende System als Ganzes an PageRank verlieren wird.
Hinzu kommt, dass der Zuwachs an PageRank, den die verlinkte Seite erfährt, auf alle nachfolgenden Seiten verteilt wird. Besteht eine Webseite also aus vielen Unterseiten, so minimiert sich der Effekt für jede einzelne.
In den meisten Fällen profitiert somit nur eine der beiden Seiten von einer derartigen Verabredung, wobei zugleich der tatsächliche Nutzen für diese Seite oft sehr gering ausfällt.
3.3 Regiert Geld den PageRank?
Kritiker führen nun an, dass finanzstarke Seitenbetreiber sich Verweise auf ihre Seiten erkaufen können und somit nicht etwa Qualität ausschlaggebend für die Positionierung in den Suchergebnissen ist sondern vielmehr die finanziellen Möglichkeiten des Betreibers.Ausgehend von den Überlegungen zum Linktausch muss in diesen Fällen also bedacht werden, dass beide Betreiber den Kosten/Nutzen Faktor eines solchen Betruges berücksichtigen sollten. Während der Betreiber der verlinkenden Seite abwägen muss, ob ihm die gebotene Summe den Verlust an PageRank wert ist, so muss der Betreiber der verlinkten Seite abschätzen, ob eine solche Investition für die ggf. minimale Änderung des PageRanks seiner Seite lohnenswert ist.
Hinzukommt, dass sich Google das Recht an manuellen Änderungen einzelner PageRank Werte vorbehält. Sollten also Betrugsversuche bekannt werden, so drohen den entsprechenden Seiten erhebliche Abzüge beim PageRank.
3.4 Der PageRank - Werkzeug für Googles wirtschaftliche Interessen?
Anders sieht es aus, wenn man die mittlerweile extrem hohe Wirtschaftsmacht von Google selbst betrachtet. Rund 90% aller Suchanfragen in Deutschland laufen über Google[4]. Das Unternehmen ist also nicht nur wirtschaftlich eine respektable Größe in der Informationstechnologie sondern besitzt durch seine Marktbeherrschende Stellung auch eine enorme Macht.Es gilt beinahe der Grundsatz, wer wer bei Google nicht gefunden werden kann, der existiert nicht. Gerade für Unternehmen spielt die Auffindbarkeit ihrer Webseiten bei der Schaffung neuer und der Pflege alter Geschäftsbeziehungen eine große Rolle. Doch keine Webseite hat das Recht auf einen hohen PageRank, ja noch nicht einmal auf die Korrekte Berechnung nach den Regeln des Algorithmuses.
Google besitzt hier eine extreme Machtstellung, und verfügt somit grundsätzlich über die Möglichkeit aufkommende Konkurrenz bereits im Keim zu ersticken. Ob und in wie weit manuelle Manipulationen am PageRank einzelner Seiten tatsächlich auf Googles urgeigenes, wirtschaftliches Interesse zurück zuführen sind bleibt aber vorerst reine Spekulation.
3.5 Fazit
Gravierende Manipulationen am PageRank einer Seite sind nur sehr schwer durch zu führen und können ggf. durch manuellen Eingriff beseitigt werden. Der Anwender sollte jedoch stets beachten, dass auch der PageRank keine Zuverlässige Aussage über die tatsächliche Qualität der angebotenen Seiten treffen kann. Eine solche Einschätzung gestaltet sich allerdings auch als extrem schiwerig und wird wohl weiterhin dem Benutzer überlassen bleiben. Demnach stellt der PageRank-Algorithmus ein gutes Verfahren dar, um verzweigte Strukturen wie das World Wide Web zu durchsuchen. Letzten Endes gibt der Erfolg des ehemaligen Studentenprojekts Google Recht.I Quellenverzeichnis
[1] Sergey Brin, Rajeev Motwani, Larry Page und Terry Winograd: The PageRank Citation Ranking: Bringing Order to the Web, Stanford Digital Library Technologies Project, 1998[2] Sergey Brin und Lawrence Page: The Anatomy of a Large Scale Hypertextual Web Search Engine, Computer Science Department, Stanford University, 1998
[3] heise online: Google legt weiter kräftig zu, 2007
[4] heise online: Google in Deutschland über 90 Prozent, 2006
