Knol steht während·planmäßiger·Wartungsarbeiten nicht zur Verfügung. Diese beginnen um Mon, 09 Nov 2009 18:30:00 GMT. Wir gehen davon aus, dass die Wartungsarbeiten um Mon, 09 Nov 2009 20:00:00 GMT abgeschlossen sein werden.
Version: Baidi441

PageRank

Der PageRank-Algorithmus von Google

Darstellung des Prinzips des PageRank-Algorithmus, der Geschichte, der zugrundeliegenden Mathematik, Manipulationsmöglichkeiten und der Bezug zur Position in den Ergebnislisten von Google.

Einführung

Der PageRank-Algorithmus ist ein Verfahren, Seiten/Dokumente allein anhand ihrer Verlinkungsstruktur ein Gewicht (PageRank) zuzuordnen. Das Grundprinzip lautet: Je mehr Links auf eine Seite verweisen, desto höher ist das Gewicht dieser Seite, je höher das Gewicht der verweisenden Seiten ist, desto größer ist der Effekt.

Inhalt, Qualität, Typ oder andere Eigenschaften spielen bei diesem Verfahren keinerlei Rolle, einzig die Verlinkung der Seiten untereinander entscheidet über den PageRank-Wert einer Seite. Der PageRank-Algorithmus stellt damit ein Verfahren dar, die Linkpopularität einer einzelnen (Web-) Seite bzw. eines Dokumentes zu messen.

Geschichte

Die Idee des PageRank-Algorithmus stammt ursprünglich aus der Soziometrie und lässt sich in der Fachliteratur 1949 bei Seeley und 1953 bei Katz nachweisen. Allerdings gibt es in diesen Beschreibungen noch keinen Dämpfungsterm, der erst 1965 von Charles H. Hubbell eingeführt wurde.

Später wurde der Algorithmus wurde von Larry Page und Sergey Brin an der Stanford Universität aufgegriffen und für das Ranking der Suchmaschinenergebnisseiten eingesetzt. Er diente der Suchmaschine Google als wichtige Grundlage für die Bewertung von Seiten und war maßgeblich für den Erfolg der Suchmaschine verantwortlich. Die Stanford University meldete 1998 das Verfahren zum Patent an.

Der Name PageRank verweist auf Larry Page.

Mathematik

Das Prinzip des PageRank-Algorithmus ist, dass jede Seite ein Gewicht (PageRank) besitzt, das umso größer ist, je mehr Seiten auf diese Seite verweisen. Das Gewicht PRi einer Seite i berechnet sich also aus den Gewichten PRj der auf i verlinkenden Seiten j. Verlinkt j auf insgesamt Cj verschiedene Seiten, so wird das Gewicht von PRj anteilig auf diese Seiten aufgeteilt. Die Berechnung des PageRank-Wertes ist die Lösung eines linearen Gleichungssystems der Form 
M * PR = ( 1 - d )
wobei 0 < d < 1 ein Dämpfungsfaktor, PR ein N-dimensionaler Vektor und M eine N x N-Matrix ist. N ist die Anzahl der Seiten des betrachteten Systems, d.h. beispielsweise alle indexierten Dokumente. Die i-te Komponente des Vektors PR, d.h. PRi, ist der PageRank der i-ten Seite. Die Matrix  M setzt sich wie folgt zusammen 
 M = 1 – d T
wobei T die Übergangsmatrix beschreibt. Die Komponenten von T ergeben sich aus der Anzahl der ausgehenden Links: 
 Tij= 1 / Cj (falls Seite j zu Seite i linkt)
 Tij= 0 (sonst)
Cj ist die Anzahl von Links auf Seite j.

Die Lösung des linearen Gleichungssystems ist 
 PR = M-1 * ( 1 – d )
Die Berechnung der inversen Matrix M-1 kann prinzipiell analytisch erfolgen. Für 0 < d <1 hat M keine Eigenwerte die Null sind, so dass die letzte Gleichung eine eindeutige Lösung hat.

Für größere Dimensionen N ist es allerdings sinnvoll (d.h. weniger zeitaufwändig) die Berechnung numerisch vorzunehmen. Dies geschieht mittels eines Iterationsschemas. Das einfachste Verfahren ist die Jacobi-Iteration 
 PR{k+1} = ( 1 –d ) + d T * PR{k}
PR{k} bezeichnet den Wert des PageRank-Vektors in der k-ten Iteration. Als Startwert kann z.B. PR{0} = 1 genommen werden. Die Konvergenz des Verfahrens ist garantiert, da der größte Eigenwert von d T kleiner als 1 ist.

Der Dämpfungsfaktor d bestimmt den Anteil des PageRank-Wertes, der weitergeleitet wird. Für d = 1 wird alles weitergeleitet, für kleinere d erfolgt eine Dämpfung. Für Werte von d nahe 1 treten allerdings Konvergenzprobleme ebi der numerische Berechnung auf. Die Anzahl der Iterationen, bis das Ergebnis stabil ist, nimmt zu. Für eine reale Berechnung des PageRanks wären ca. 100 Iterationen nötig. Natürlich ist die genaue Anzahl auch von der Verlinkungsstruktur und der gewünschten Genauigkeit abhängig. Die Anzahl der Iterationen kann reduziert werden, wenn als Ausgangswert z.B. das Endergebnis der letzen Iterationen genommen wird (vorausgesetzt die Verlinkungsstruktur hat sich in der Zwischenzeit nicht grundsätzlich geändert).

Schreibt man die Gleichung in Komponenten und lässt die Bezeichnung für die Nummer der Iteration weg, so ergibt sich 
 PRi= ( 1 – d ) + d ( PRX1 / CX1 + ...+ PRXn / CXn )
Die letzte Gleichung wird oftmals auch als der PageRank-Algorithmus bezeichnet, da sie in dieser Form von Brin und Page angegeben wurde. Genau genommen ist allerdings nur ein Iterationsschema zur numerischen Lösung der obigen Matrixinversion.

Die Jacobi-Iteration ist ein einfaches, allerdings nicht das schnellste Verfahren. Daneben gibt eine Anzahl weiter Iterationsschemata zur Matrixinversion  wie minimal residue, Gauss-Seidel, Überrelaxationsverfahren, Konjugierte-Gradienten-Verfahren, Präkonditionierung, Multigrid und Blocking Techniken or Chebyshev. Allerdings sind einige dieser Methoden auf hermitesche Matrizen beschränkt.

In einigen Fällen wird alternativ auch das Gleichungssystem 
 M * PR = ( 1 - d ) / N
betrachtet. Offensichtlich ergibt sich der gleiche Lösungsvektor nur mit einer anderen Normierung ( 1 / N ). Dies entspricht dem Fall, dass der gesamte PageRank des Systems auf 1 normiert wird (Probleme mit Seiten ohne ausgehende Links werden dabei nicht berücksichtigt).

Einen Sonderfall stellt der Fall d = 1 (d.h. keine Dämpfung) dar. In diesem Fall wird der Eigenvektor der Matrix T mit dem Eigenwert eins gesucht. Das Problem sind degenerierte Eigenwerte. Diese treten immer auf, falls die Verlinkungsstruktur so ist, dass nicht jede Seiten von jeder anderen aus erreicht werden kann. Dies ist der Fall, wenn es tote Enden gibt (d.h. Seiten ohne ausgehende Links) oder geschlossene Strukturen existieren. Das Endergebnis der Iteration ist in diesem Fall von den Anfangswerten abhängig und ist eine Kombination der verschiedenen Eigenvektoren mit Eigenwert 1. Für d < 1 stellen tote Ende kein Problem dar und brauchen nicht gesondert behandelt zu werden.


Zufallssurfer-Modell

Normiert man den gesamten PageRank des Systems auf 1, so entspricht das Gewicht/der PageRank einer Seite der Wahrscheinlichkeit, dass ein zufälliger Surfer sich auf dieser Seite befindet. Ein zufälliger Surfer bewegt sich durch das System, indem er mit der Wahrscheinlichkeit d zufällig einen der ausgehenden Links der aktuellen Seite und mit Wahrscheinlichkeit 1 − d eine beliebige neue Seite wählt. Um Probleme mit Seiten ohne ausgehende Links zu vermeiden, können bei diesen Links zu allen vorhandenen Seiten hinzugefügt werden.


Einfaches Beispiel

Im folgenden ist ein einfaches Beispiel von elf Dokumenten mit einer simplen Verlinkungsstruktur und der daraus resultierenden PageRank-Verteilung zu sehen:

Größere Smileys entsprechen einem höheren PageRank, wobei die Größe jedoch nicht proportional zum PageRank gewählt wurde. Es wird deutlich, dass die Anzahl und der Links und das Gewicht der verlinkenden Seite für den PageRank entscheidend ist.

Anzeige

Informationen über den realen PageRank lassen sich nur aus der Google-Toolbar und dem Google-Verzeichnis entnehmen. Der von Google in der Toolbar angezeigte PageRank liegt zwischen 0 und 10. Der im Google-Verzeichnis angegebene Wert lag bis Anfang 2008 zwischen 0 und 7, entspricht inzwischen aber dem in der Toolbar angezeigten Wert. Diese Werte bilden den realen PageRank auf einer logarithmischen Skala ab und geben das Ergebnis als gerundeten ganzzahligen Wert wieder.

Alle anderen Dienste, die einen Anzeige des PageRank ermöglichen, greifen auf die in der Toolbar angezeigten Werte zurück.

Der in der Google-Toolbar angezeigte PageRank wurde früher alle dreißig Tage aktualisiert. Inzwischen ist die Zeitspanne zwischen den Updates angestiegen, auf ungefähr drei Monate. Die Abstände der Updates können allerdings im Einzelfall auch stark abweichen. Zudem spiegelt auch zum Zeitpunkt des Updates der Toolbar-Wert nicht den aktuellen Wert , sondern einen einigen Wochen alten wider. Der eigentliche (interne) PageRank, der auch für das Ranking der Webseiten verwendet wird, wird dagegen permanent aktualisiert.


Manipulation

Aufgrund der wirtschaftlichen Bedeutung ist es inzwischen zu gezielten Manipulationen und Fälschungen gekommen. Durch Weiterleitung auf bestehende Seiten mit hohem PageRank wird gezielt versucht, die Anzeige in der Google-Toolbar zu manipulieren (im Englischen als "false PageRank" oder "spoofed PageRank" bezeichnet). In diesen Fällen zeigt die Toolbar den Wert der Zielseite an. Dies bleibt auch nach Entfernung der Weiterleitung so, so dass Besuchern ein falscher, in der Regel höherer, Wert angezeigt wurde. Für die Platzierung in den Ergebnisseiten der Suchmaschinen hat dies keine Auswirkungen, lediglich der angezeigte Wert ist falsch. Dies soll u.a. dazu dienen, bei dem Verkauf von Links zu anderen Webseiten den Preis zu erhöhen. Manipulationen lassen sich durch Eingabe der Suchfunktion 'info:URL' bei Google erkennen (z.B. info:knol.google.com). Stimmt die von Google in grün angezeigte URL nicht mit der angegebenen überein, so wurde (oder wird) die Seite weitergeleitet. Allerdings muss eine Weiterleitung nicht notwenigerweise ein Manipulationsversuch sein, sondern kann eine Vielzahl von Ursachen haben - beispielsweise technische Gründe aufgrund des verwendeten Content Management Systems.

Außerdem wurde das System von Suchmaschinenoptimierern durch das Spamming von Weblinks in Gästebüchern, Blogs und Foren sowie dem Betreiben von Linkfarmen und anderen unseriösen Methoden unterlaufen. All diese Methoden dienten zur Verbesserung des PageRank der verlinkten Zielseite. Anfang 2005 implementierte Google mit rel="nofollow" ein neues Attribut für Verweise, als Versuch, gegen Spam vorzugehen. Links, die mit diesem Attribut versehen werden, werden nicht für die PageRank-Berechnung berücksichtigt. Durch Kennzeichnung ausgehender Links kann so beispielsweise dem Gästebuch-, Blog- und Forum-Spamming entgegengewirkt werden. Allerdings ist diese Methode umstritten. So wird bemängelt, dass Spam angeblich nicht vermindert wird, das Attribut nur für Suchmaschinen aber nicht für Menschen nützlich ist und das Setzen berechtigter Links diskriminiert.


Beeinflussung

Für den Betreiber einer Webseite gibt es verschieden Möglichkeiten den PageRank zu beeinflussen.

Zum einen kann über die interne Linkstruktur die Verteilung auf der eigenen Seite gesteuert werden. So können Deep-Links zu wichtigen Unterseiten deren Wert erhöhen. Andererseits können unwichtige Seiten, wie beispielsweise die Impressum-Seite, mit einem nofollow-Attribut versehen werden, um deren Wert zu verringern. Beide Methoden verändern die interne Verteilung des PageRank, nicht aber den PageRank der gesamten Webseite, d.h. die Summe des PageRank-Wertes aller Unterseiten.

Den PageRank insgesamt lässt sich nur durch zusätzliche externe Links erhöhen. Dies kann beispielsweise durch den Eintrag in Webkataloge wie dem ODP (Open Directoy Project, DMOZ) oder bei Social-Bookmark-Diensten wie del.ico.us oder Mister Wong geschehen. Voraussetzung ist, das externe Links bei diesen Webseiten nicht mit dem nofollow-Attribut versehen sind oder durch eine Weiterleitung auf eine per robots.txt geschützten Datei geblockt werden. Natürlich kann auch bei geblocktem PageRank ein Eintrag sinnvoll sein, da er zu zusätzlichen Besuchern verhelfen kann. In jedem Fall sollten bei dem Eintrag die Richtlinien der jeweiligen Dienste beachtet werden.

Eine weitere Möglichkeit ist der Linktausch mit anderen Webseiten. Linktausch führt jedoch nicht automatisch zu höheren Werten. Hier spielt bei der Betrachtung der genaue Wert der tauschenden Seiten eine entscheidende Rolle. So kann sich der Wert erhöhen, ungefähr gleich bleiben oder sich auch verringern. Natürlich gibt es auch unabhängig vom PageRank Argumente für einen Linktausch. So kann sich, selbst bei verringertem PageRank, die Position in den Suchmaschinen erhöhen. Außerdem kann ein Linktausch zu zusätzlichen Besuchern führen. Die Teilnahme an Linktauschprogrammen verletzt jedoch die Richtlinien vieler Suchmaschinenbetreiber (wie z.B. Google).

Ranking

Für das Ranking einer Webseite in den Ergebnisseiten von Google und damit für die Suchmaschinenoptimierung spielen und spielten nicht nur der PageRank, sondern auch sehr viele andere Faktoren eine Rolle. Hierzu zählen "On-Page-Faktoren" wie Überschriften oder Titel und "Off-Page-Faktoren" (zu denen auch der PageRank zählt) wie eingehender Linktext. Bei der Betrachtung des Zusammenhangs zwischen PageRank und Position in den Ergebnissen ist auch zu beachten, dass der in der Toolbar angezeigte Wert nicht aktuell ist sowie auf einer logarithmischen Skala gerundet dargestellt wird. Intern, d.h. auch für das Ranking der Webseiten, verwendet Google den aktuellen realen und nicht den in der Toolbar angezeigten Wert.

Aktuelle Situation

Der heute von Google verwendete Algorithmus für die Berechnung der Linkpopularität hat nicht mehr die hier beschriebene Form, geht aber auf diese Formel zurück. So wurden z.B. Modifikationen vorgenommen, die das Generieren von PageRank durch die Erzeugung massenhafte Webseiten verhindern.


Quellen

Kommentare

©2009 Google