Kleinbergs HITS

Das HITS-Verfahren („Hyperlink induced topic search"; auch „Kleinberg-Algorithmus") versucht, die Einschränkungen einfacher Linkzählungen bzw. die themenunabhängige Bewertungen von Webseiten zu überwinden. Es sollen die wichtigsten Seiten (sog. Autoritäten) passend zum Thema der jeweiligen Suchanfrage ermittelt werden, zusätzlich werden Seiten ermittelt, die auf viele Autoritätden verweisen (die sog. Hubs, also „Mittelpunkte“).
Das Verfahren wird in Kleinberg (1999) beschrieben. Ausgangspunkt für die Berechnung der wichtigsten Seiten zu einem Thema soll eine Ausgangsmenge S_ sein, die die folgenden drei Bedingungen erfüllen soll (Kleinberg 1999, 608):
1. S? soll relativ klein sein. Dies ist notwendig, um auf diese Menge komplexe Algorithmen in vertretbarer Rechenzeit anwenden zu können.
2. S? soll viele relevante Seiten enthalten. Dies macht es leichter, die gesuchten Autoritäten zu finden. Es wird angenommen, dass die besten Autoritäten innerhalb der Menge S? stark referenziert werden.
3. S? soll die meisten (oder zumindest viele) der stärksten Autoritäten enthalten.
In einem ersten Schritt werden relevante Seiten durch ein textbasiertes Verfahren identifiziert. Kleinberg verwendet hierfür Ergebnisse der Suchmaschine AltaVista, die zum Zeitpunkt seiner Untersuchungen Verfahren des klassischen Information Retrieval wie in Kap. 5.4 beschrieben einsetzte. Mit dieser Methode wird ein Root Set R? ermittelt, welches aus etwa 200 Dokumenten besteht. Kleinberg zeigt, dass im Root Set die Dokumente untereinander oft nur schwach verlinkt sind (Kleinberg 1999, 608). Er geht davon aus, dass im Root Set zwar nicht alle guten Autoritäten enthalten sind, auf diese jedoch ziemlich wahrscheinlich von Dokumenten des Root Sets aus verwiesen wird.
Um sicherzustellen, dass die Autoritäten in der tatsächlichen Treffermenge überhaupt enthalten sind, wird das Root Set zum Base Set S? erweitert. Dieses enthält neben den Dokumenten des Root Set auch alle Seiten, die auf eine Seite im Root Set verweisen sowie alle Seiten, auf die von einem Dokument des Root Set aus verwiesen wird. Die Erweiterung des Root Set zum Base Set ist in Abbildung 8.4 dargestellt.
Das Base Set erfüllt laut Kleinberg nun alle drei oben angeführten Bedingungen für die Ausgangsmenge. Die Größe des Base Set liegt in etwa zwischen 1.000 und 5.000 Dokumenten.
In einem Zwischenschritt werden nun noch einige Links für die weitere Berechnung ausgeschlossen. Kleinberg unterscheidet hier zwischen externen Links (transverse links), welche auf ein Dokument einer anderen Domain verweisen und internen Links (intrinsic links), die auf ein Dokument der gleichen Domain verweisen (Kleinberg 1999, 610). Alle internen Links werden ausgeschlossen, da sie oft nur Navigationszwecken dienen und nicht der gewünschten Referenz auf eine Autorität. Das Ergebnis ist ein neuer Graph G?, der sowohl viele relevante Seiten als auch starke Autoritäten enthält. Die Autoritäten werden im Weiteren aus der Linkstruktur von G? berechnet.
Kleinberg verwirft die reine Zählung von In-Links, da bei diesem Verfahren auch Dokumente zu Autoritäten gemacht werden würden, die themenunabhängig populär sind. Der Sinn des Verfahrens liegt allerdings gerade darin, die in Bezug auf die eingegebene Suchanfrage wichtigsten Seiten zu finden.

Abb. 8.4. Erweiterung des root set zum base set (Kleinberg 1999, 609)

Trotzdem ist es möglich, ohne die Analyse des Inhalts der Dokumente allein auf Basis der Linkstruktur die gesuchten Autoritäten zu finden. Charakteristisch für die Autoritäten ist, dass sie viele In-Links auf sich ziehen und außerdem eine deutliche Überschneidung zwischen den Seiten, die auf die Autoritäten verweisen, besteht. Abbildung 8.5 zeigt den Gegensatz von echten Authorities zu Seiten, die sich nur durch viele In-Links auszeichnen. Die echten Authorities werden daran erkannt, dass besondere Seiten existieren, die auf verschiedene Authorities verweisen. Zwischen den von diesen Seiten gesetzten Links müssen Überschneidungen bestehen, um Authorities klar identifizieren zu können.
Für die verweisenden Seiten führt Kleinberg das Konzept der Hubs ein. Dies sind Seiten, die auf mehrere relevante Autoritäten verweisen. Hubs und Authorities bedingen sich gegenseitig: „A good hub is a page that points to many good authorities; a good authority is a page that is pointed to by many good hubs" (Kleinberg 1999, 611). Die Berechnung von Hubs und Authorities muss also in einem rekursiven Verfahren erfolgen, um die bestehende Zirkularität aufzulösen.
Der beschriebene Algorithmus berechnet für jede Seite sowohl deren Hub-Gewicht y<p> als auch deren Authority-Gewicht x<p>. 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 In-Links mit hohem Hub-Gewicht auf sich zieht (Kleinberg 1999, 611).
Das Authority-Gewicht einer Seite ist damit die Summe der Hub-Gewichte der Seiten, die auf sie verweisen. Das Hub-Gewicht einer Seite ist dagegen die Summe der Authority-Gewichte der Seiten, auf welche diese verweist.

Abb. 8.5. Hubs und Authorities im Gegensatz zu Seiten mit vielen In-Links (Kleinberg 1999, 611)

Um nun die Hub- und Authority-Gewichte zu berechnen, müssen zuerst Ausgangswerte festgelegt werden, auf deren Basis dann in einem iterativen Verfahren die Werte in jedem Schritt weiter angenähert werden. In jedem Schritt werden die vorläufigen Hub- und Authority-Gewichte weiter angenähert. Wie bei solchen Verfahren üblich, ändern sich die Werte nach einer gewissen Anzahl von Durchläufen nur noch geringfügig; im beschriebenen Verfahren sollen 20 Durchläufe ausreichen (Kleinberg 1999, 614).
Das Ergebnis sind für jede Seite ein Hub- und ein Authority-Gewicht. Seiten mit starken Authority-Gewichten sind in der Regel nur schwache Hubs, während starke Hub in der Regel nur ein geringes Authority-Gewicht auf sich ziehen können. Kleinbergs Verfahren ist deshalb nicht nur für die Feststellung der „wichtigsten" Seiten zu einer Suchanfrage von Bedeutung, sondern - vor allem auf lange Frist gesehen - auch für die Unterteilung von Web-Dokumenten in zwei Klassen. Keines der herkömmlichen Verfahren ist in der Lage, die Dokumente prinzipiell nach ihrer Funktion zu unterscheiden. Die Methode von Kleinberg liefert dem Nutzer zwei Zugänge zu den im Web vorhandenen Informationen: Einerseits kann er in einem Schritt die automatisch ermittelten wichtigen Seiten angezeigt bekommen, andererseits kann er über die Auswahl der Hubs Übersichtsseiten zum Thema finden, die einen Sucheinstieg zu den bedeutenden Quellen bieten.
Problematisch bei der Ermittlung von Hubs und Authorities sind sog. mixed hubs, also Linkseiten, die mehrere Themen behandeln. Chakrabarti (2003, 223) zeigt als Beispiel eine Linksammlung, die sich mit britischen und irischen Schriftstellern beschäftigt, wobei dem Werk Shakespeares ein eigener Bereich innerhalb der Liste gewidmet ist. Eine solche Seite könnte von Kleinbergs Algorithmus als ein Hub zum Thema Shakespeare angesehen werden und die durch diese Seite verlinkten Dokumente irrtümlich mit in das Base Set aufgenommen werden. Dadurch würden Seiten, die andere britische Schriftsteller behandeln als dem Thema Shakespeare zugehörig angesehen werden.
Es bleibt festzuhalten, dass in der bisherigen Forschung die Unterteilung von Webseiten nach ihrer Art noch nicht ausreichend berücksichtigt wurde. Ähnlich der von Kleinberg getroffenen Unterscheidung könnten weitere Unterteilungen getroffen werden, die beispielsweise die Relevanz von Dokumenten für Suchanfragen gemäß ihres Anfragetyps nach der Unterscheidung von Broder (2002; vgl. Kap. 2.5) treffen könnten.
Die Ideen Kleinbergs sind in der Suchmaschine Teoma umgesetzt. Inwieweit das Ranking in dieser Suchmaschine exakt nach dem Kleinberg-Algorithmus abläuft, kann rekursiv nicht überprüft werden; klar ist jedoch, dass sich Teoma die Unterscheidung von Hubs und Authorities zu eigen gemacht hat. Ein frühes Paper über diese Suchmaschine (damals noch unter dem Namen „DiscoWeb") bezieht sich explizit auf Kleinbergs Text (Davison et al. 1999). Den Entwicklern dieser Suchmaschine ist es gelungen, die relativ komplizierte (also zeitaufwendige) Berechnung der Hubs und Authorities „on the fly“ in einer vertretbaren Zeit möglich zu machen. Die Trefferlisten bei Teoma werden unterteilt in results, resources und Vorschläge zur Verbesserung der Suchanfrage. Unter results werden die u.a. nach ihrer Autorität sortierten Suchergebnisse angezeigt, die resources entsprechen den Kleinberg'schen hubs. Abbildung 8.6 zeigt ein Beispiel einer Trefferliste von Teoma für die Suchanfrage „information science“.

Abb. 8.6. Darstellung der Ergebnisse bei Teoma