Was ist der Hilltop-Algorithmus?
Der Hilltop-Algorithmus wurde von Bharat und Mihaila (damals Universität Toronto) entwickelt und 1999 veröffentlicht. 2003 hat Google das Patent an dem Algorithmus erworben.
Beim Hilltop-Algorithmus werden Dokumente anhand Ihrer eingehenden Links von so genannten Experten-Seiten bewertet. Experten-Seiten zu einem bestimmten Thema zeichnen sich dadurch aus, dass sie Links zu vielen unabhängigen Seiten zu diesem Thema besitzen. Seiten sind unabhängig, wenn sie von verschiedenen Autoren von unabhängigen Organisationen stammen. Beispiele für Experten-Seiten sind gut geführte Verzeichnisse. Webseiten, zu denen viele der besten Experten-Seiten verweisen, werden als Autoritäten behandelt und gut gelistet.
Details
Der Bestimmung von Expertenseiten kommt beim Hilltop-Algorithmus eine große Bedeutung zu. Eine Expertenseite zeichnet sich dadurch aus, dass sie zu vielen unabhängigen Seiten zu einem Thema verlinkt. Die Bestimmung der Abhängigkeiten ist deshalb ein zentraler Punkt. In der Original-Implementierung werden Seiten als abhängig angesehen, wenn sie zum gleichen Class-C Netz gehören (erste drei Blöcke der IP-Adresse stimmen überein) oder den gleichen Domainnamen haben (z.B. www.ibm.com und www.ibm.co.uk). Weiterhin ist die Beziehung transitiv, d.h. falls A in Verbindung zu B und B in Verbindung zu C steht, so stehen A und C in Verbindung. Experten-Seiten werden dadurch definiert, dass sie zu mehreren (in der Original-Version mindestens 5) unabhängigen Webseiten eines Themas verweisen.
Wie wurde im Hilltop Algorithmus die Websitequalität bewertet?
Für die Bewertung der Webseiten werden die besten Experten-Seiten herangezogen (im zitierten Dokument 200 verschiedene). Für Webseiten, auf die mindestens zwei verschiedene Experten-Seiten verlinken, wird dann ein Relevanz-Wert berechnet. Diese Seiten werden als Autoritäten bezeichnet. Der Relevanz-Wert für eine Seite richtet sich nach der Anzahl und Relevanz der verweisenden Experten-Seiten. Die Ordnung der Autoritätsseiten erfolgt entsprechend ihres Relevanz-Wertes.
Suchmaschinenoptimierung
Eine Suchmaschinenoptimierung wird beim Hilltop-Algorithmus dadurch erreicht, dass man viele Links von Experten-Seiten sammelt. Deshalb sollte die zu optimierende Webseite in möglichst viele Verzeichnisse zu dem Thema eingetragen sein. Weitere Experten-Seiten findet man, indem man nach Seiten sucht, die gleichzeitig auf viele top-platzierte Webseiten verweisen.
Gleichzeitig sollte versucht werden, selber Experten-Seiten aufzubauen, d.h. beispielsweise eigene Verzeichnisse zu diesem Thema zu schaffen, und die zu optimierende Webseite einzutragen.
Was ist der Trustrank-Algorithmus?
Der TrustRank-Algorithmus (trust: Vertrauen) ist ein Verfahren zur Bewertung der Qualität von Webseiten, dass 2004 von Gyongyi, Garcia-Molina und Pedersen veröffentlicht wurde. Der Grundgedanke des Algorithmusses ist ähnlich wie beim PageRank-Algorithmus: Durch die Verlinkungsstruktur wird ein Maß für die Qualität einer Webseite generiert. Der Algorithmus kann als eine Weiterentwicklung des PageRank-Verfahrens angesehen werden. Dabei ist Weiterentwicklung nicht notwendigerweise mit Verbesserung gleichzusetzen.
Das Verfahren basiert darauf, dass eine Anzahl von vertrauenswürdigen Webseiten per Hand ausgewählt wird. Diese dienen als Quellen für die Vertrauenswürdigkeit und können diese weitergeben. Das Maß für die Vertrauenswürdigkeit propagiert dabei in gleicher Weise wie der PageRank. Zusätzlich können auch noch Quellen für Spam gekennzeichnet werden. Dieses negative Maß (auch inverser PageRank) propagiert dann rückwärts und stellt ein Maß für die Unseriosität dar. Beide Werte können für eine Bewertung kombiniert werden.
Der PageRank Algorithmus
Die Berechnung des PageRanks 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. 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 lassen 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 Pageranks, der weiter transferiert 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 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. Genau genommen ist allerdings nur ein Iterationsschema zur numerischen Lösung der obigen Matrixinversion. Die Jacobi-Iteration ist einfach, allerdings nicht das schnellste Verfahren. So konvergiert beispielsweise das folgende Iterationsschema (minimal residue)
PR{k+1} = PR{k} + R{k} ( ? Ri Mij Rj) /
( ? Min Rn Mij Rj)
mit
R{k+1} = R{k} – M * R{k} ( ? Ri Mij Rj) /
( ? Min Rn Mij Rj)
i.A. schneller. Daneben gibt eine Anzahl weiter Iterationsschemata zur Matrixinversion (s. z.B. A. S. Householder. “The Theory of Matrices in Numerical Analysis” New York, 1964) wie 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 ).
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.
Random-Surfer-Modell
Eine anschauliche Interpretation des PageRanks (für d < 1) ist das Random-Surfer-Modell: Ein Surfer startet auf einer zufälligen Seite und bewegt sich dann durch das Netz, indem er mit der Wahrscheinlich d zufällig einem Link auf der Seite folgt bzw. mit der Wahrscheinlichkeit (1-d) auf einer beliebigen Seite neu startet. Falls es keine toten Enden gibt, so entspricht die Wahrscheinlichkeit auf Seite i zu landen genau dem PageRank des Gleichungssystems
M * PR = ( 1 – d ) / N
Gibt es in dem System solche toten Enden, so ist der Wahrscheinlichkeits-Vektor proportional zum PageRank-Vektor.
Der Beitrag SEO Rückblick: Hilltop-, Trustrank- und PageRank Algorithmus erschien zuerst auf Wolf of SEO.
from Wolf of SEO https://wolf-of-seo.de/blog/hilltop-trustrank-und-pagerank-algorithmus/
Keine Kommentare:
Kommentar veröffentlichen