Gastautor 31. Januar 2006

Wie Suchmaschinen funktionieren – Teil 6: Das Gegenmodell : Kleinbergs Hubs & Authorities

Kein Beitragsbild

von Dirk Lewandowski

Im gleichen Jahr wie das Konzept von PageRank erschien ein weiterer Artikel, der ein bahnbrechendes linktopologisches Verfahren darstellte. Der Autor: Jon Kleinberg. Der Name des Verfahrens: „Hypertext-Induced Topic Search“, auch HITS genannt. Kleinbergs Idee bildet quasi das „Gegenmodell“ zu PageRank und unterscheidet sich von diesem in seiner Ausführung, nicht aber in seinem Ziel: die besten Seiten im Ranking nach vorne zu bringen.

„Einfache“ linktopologische Verfahren wie PageRank haben nicht nur Vorteile. Sie sind zwar stark darin, die Popularität einer bestimmten Seite zu messen; ob diese Seite aber tatsächlich etwas mit dem Thema der gerade gestellten Suchanfrage zu tun hat, berücksichtigen sie jedoch nicht. Vielmehr ist der PageRank ein statischer Wert, der nur alle paar Monate neu berechnet wird und sich zwischenzeitlich nicht ändert.

Er gehört daher zu den anfragenunabhängigen Rankingfaktoren. Damit lässt sich auch erklären, warum Dokumente von bestimmten Sites (wie etwa Wikipedia) besonders oft vorne in den Trefferlisten stehen: Allein aufgrund der inneren Verlinkung der Website, deren Startseite einen extrem hohen PageRank erreicht hat und der damit einhergehenden Vererbung eines Teils des PageRanks erreichen diese Dokumente einen hohen Popularitätswert. Sie erscheinen weit oben in der Trefferliste, obwohl vielleicht andere Dokumente für die eingegebenen Suchbegriffe relevanter wären.

Im Gegensatz zu Verfahren wie PageRank berücksichtigt Kleinbergs HITS die eingegebene Suchanfrage und ist also anfrageabhängig. Es wird versucht, die wichtigsten Seiten aufgrund der Verlinkungsstruktur zu finden – hier wird allerdings nur die Verlinkungsstruktur der thematisch relevanten Seiten ausgewertet, nicht (wie im Fall von PageRank) die des gesamten Web. Nur Links von Seiten, die selbst für die eingegebene Suchanfrage relevant sind, werden gezählt.

Damit ist leider auch schon ein Nachteil des Verfahrens klar. Wird eine Suchanfrage eingegeben, muss die Linkpopularität live berechnet werden, während andere Verfahren einfach auf einen Wert, der lange vorher ausgerechnet wurde, zurückgreifen. Da eine solche Berechnung relativ aufwendig ist, führt sie zur Verzögerung bei der Ergebnisausgabe.

Kleinbergs Verdienst liegt nicht nur darin, ein gutes linktopologisches Verfahren entwickelt zu haben, sondern auch in seiner Unterscheidung von Webseiten nach Hubs und Authorities. Authorities sind dabei Seiten, die von anderen Seiten als besonders wichtig für ein Thema betrachtet werden, beispielsweise Texte, die sich mit dem gesuchten Thema auseinandersetzen.

Hubs (Mittelpunkte) dagegen behandeln das Thema auf eine andere Weise: Sie verweisen auf viele Authorities und stellen damit eher Linksammlungen als eigenständige Texte dar. Kleinbergs Modell geht davon aus, dass sich beide Formen gegenseitig bedingen: Eine Authority zeichnet sich dadurch aus, dass viele Hubs auf sie verweisen, während sich ein guter Hub dadurch auszeichnet, dass er auf viele Authorities verweist.

Aber schauen wir uns an, wie die Berechnung funktioniert. In einem ersten Schritt wird eine Ausgangsmenge an Dokumenten ermittelt, indem die Anfrage mittels textbasierter Verfahren (Kleinberg verwendet hier die Suchmaschine AltaVista) ausgewertet wird. Diese Ausgangsmenge soll etwas 200 Dokumente umfassen. Es wird angenommen, dass in dieser Menge bereits einige relevante Authorities enthalten sind, jedoch noch nicht alle. Deshalb wird die Ausgangsmenge (root set) um alle Dokumente erweitert, die entweder auf ein Dokument in der Ausgangsmenge linken oder auf die von der Ausgangsmenge aus verlinkt wird.

Diese Erweiterung wird in Abbildung 1 verdeutlicht; das so entstandene Base Set ist deutlich größer als die Ausgangsmenge und enthält in der Regel zwischen 1000 und 5000 Dokumenten. Aus der Menge entfernt werden alle Dokumente, die durch interne Links (also Links vom gleichen Server) verweisen. Dadurch soll verhindert werden, dass thematisch irrelevante Links – also beispielsweise solche, die nur zum Zweck der Navigation dienen – mit in die folgenden Berechnungen eingehen.

Screenshot
Abbildung 1 – Quelle: Kleinberg, J. (1999): Authoritative Sources in a Hyperlinked Environment. Journal of the ACM 46(5), 604-632

Kleinberg geht davon aus, dass die neue Menge nun die gesuchten Autoritäten enthält. Diese müssen allerdings aus den Tausenden von Dokumenten ermittelt werden. Wie dies allein durch die Auswertung der Linkstruktur möglich ist, zeigen die folgenden Berechnungen.

Und hier spielt das zweite Konzept Kleinbergs, die Hubs, eine Rolle. Es sollen nämlich auch in der beschränkten Menge nicht alle Links gezählt werden, sondern es sollen nur die Links von den Hubs zur Berechnung der Authorities genutzt werden. Wie sich die Verlinkungsstruktur von Hubs von einer einfachen Anhäufung von Links unterscheidet, zeigt Abbildung 2. Rechts ist die einfache Anhäufung zu sehen: Die Links kommen von irgendwo her.

Screenshot
Abbildung 2 – Quelle: Kleinberg, J. (1999): Authoritative Sources in a Hyperlinked Environment. Journal of the ACM 46(5), 604-632

Im Gegensatz dazu zeigt die linke Seite der Abbildung ein für Hubs typisches Merkmal: Sie verweisen auf mehrere Authorities! Und umgekehrt: Authorities erhalten Links von mehreren Hubs.
Im Folgenden wird für jedes Dokumente sowohl ein Hub- als auch ein Authority-Gewicht berechnet. Beide Gewichte verstärken sich dabei gegenseitig: Eine Seite erhält ein hohes Hub-Gewicht, wenn sie auf viele Seiten mit hohem Authority-Gewicht verweist.

Umgekehrt erhält eine Seite ein hohes Authority-Gewicht, wenn sie viele Links mit hohem Hub-Gewicht auf sich ziehen kann.
Ähnlich wie beim PageRank müssen die Gewichte am Anfang mit Ausgangswerten festgelegt und anschließend in einem iterativen Prozess angenähert werden. Nach einigen Durchläufen bleiben die Werte relativ konstant und die Berechnung kann abgebrochen werden. Kleinberg spricht von 20 Durchläufen, bis stabile Werte erreicht sind.

Das Ergebnis der Berechnung besteht immer aus zwei Bereichen: Den besten Hubs und den besten Authorities. Letztere bilden quasi die Trefferliste, wie man sie gewohnt ist: Die wichtigsten Texte zum Thema werden absteigend nach Relevanz sortiert angezeigt. Daneben wird aber eine weitere Trefferliste generiert, die die besten Quellensammlungen zum Thema anzeigt und dem Nutzer einen neuen Sucheinstieg präsentiert.

Implementiert ist Kleinbergs Verfahren in der Suchmaschine Teoma (seit 3/06 ask.com). Dort bekommt man neben der normalen Trefferliste unter dem Label „Resources: Links collections from experts and enthusiasts“ die Kleinbergschen Hubs angezeigt. Das funktioniert aufgrund der starken Fokussierung auf englischsprachige Dokumente in dieser Suchmaschine bei der Eingabe deutschsprachiger Suchanfragen leider nicht besonders gut; sucht man aber beispielsweise nach „Usability“, werden in der Resources-Liste einige gute Linklisten angezeigt, die viele weitere gute Quellen enthalten.

Screenshot
Suchmaschine Teoma

PageRank oder Kleinbergs HITS – welches System ist nun das bessere? Leider lässt sich das nicht so einfach entscheiden. Für Kleinberg spricht sicher die thematische Orientierung und die Unterteilung in Hubs und Authorities. Allerdings hat das System auch Nachteile, die insbesondere in der Bestimmung der Ausgangsmenge liegen. Nicht immer funktioniert die Erweiterung vom Root Set zum Base Set gleich gut; manchmal kommt es zu thematischen Verschiebungen, die alle weiteren Berechnungen wertlos machen.

Da in allen echten Suchmaschinen, in denen die linktopologischen Verfahren implementiert sind, auch viele andere Faktoren eine Rolle für das Ranking spielen, ist ein direkter Vergleich nicht möglich; vergleichen lassen sich nur die ganzen Suchmaschinen miteinander. ™

Erstveröffentlichung 31.01.2006

Dr. Webs exklusiver Newsletter
Hinweise zum Datenschutz, also dem Einsatz von Double-Opt-In, der Protokollierung der Anmeldung, der Erfolgsmessung, dem Einsatz von MailChimp als Versanddienstleister und deinen Widerrufsrechten findest du in unseren Datenschutzhinweisen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Kennst du schon unseren Newsletter?

Hinweise zum Datenschutz, also dem Einsatz von Double-Opt-In, der Protokollierung der Anmeldung, der Erfolgsmessung, dem Einsatz von MailChimp als Versanddienstleister und deinen Widerrufsrechten findest du in unseren Datenschutzhinweisen.