PageRank- und HITS-Algorithmen

PageRank und HITS sind Link-Analyse-Algorithmen, die die Wichtigkeit oder Autorität von Webseiten aus der Struktur des Hyperlink-Graphen und nicht nur aus dem Seiteninhalt schätzen.

Definition

PageRank weist jeder Seite einen anfrageunabhängigen Wichtigkeitswert zu, der ihrer stationären Wahrscheinlichkeit unter einem zufälligen Surfer entspricht, der ausgehenden Links mit einer Dämpfungswahrscheinlichkeit folgt und ansonsten teleportiert, während HITS für einen anfrageabhängigen Untergraphen Autoritätswerte für Seiten mit wertvollem Inhalt und Hub-Werte für Seiten berechnet, die auf gute Autoritäten verlinken, wobei sich beide gegenseitig verstärken.

Scope

Dieses Thema behandelt die beiden grundlegenden Link-Analyse-Algorithmen: PageRank, ein anfrageunabhängiges Maß für die Seitenwichtigkeit, basierend auf einem Random-Surfer-Modell mit Teleportation, und HITS, ein anfrageabhängiges Schema, das sich gegenseitig verstärkende Hub- und Autoritätswerte berechnet. Es behandelt die zugrunde liegenden Random-Walk- und Eigenvektor-Formulierungen, die Rolle von Dämpfung und Teleportation, Konvergenz und themenspezifische Varianten. Es schließt aus, wie diese Werte mit Textmerkmalen zu einem endgültigen Ranking kombiniert werden, was zum Web-Suchranking gehört.

Core questions

• Wie definiert das Random-Surfer-Modell PageRank als stationäre Verteilung?
• Warum ist ein Dämpfungs- oder Teleportationsfaktor notwendig, damit PageRank wohldefiniert ist?
• Wie verstärken sich Hub- und Autoritätswerte in HITS gegenseitig?
• Wie werden diese Werte iterativ berechnet und wann konvergieren sie?
• Wie unterscheiden sich PageRank und HITS in Bezug auf anfrageunabhängige versus anfrageabhängige Bewertung?

Key concepts

• PageRank
• Random-Surfer-Modell
• Dämpfungsfaktor und Teleportation
• stationäre Verteilung / Haupt-Eigenvektor
• HITS
• Hubs und Autoritäten
• anfrageunabhängige vs. anfrageabhängige Bewertung
• Potenziteration und Konvergenz

Key theories

PageRank Random-Surfer-Modell

Die Modellierung eines Surfers, der Links mit einer Wahrscheinlichkeit folgt, die einem Dämpfungsfaktor entspricht, und ansonsten zu einer zufälligen Seite springt, ergibt eine Markow-Kette, deren eindeutige stationäre Verteilung Seiten nach langfristiger Besuchshäufigkeit bewertet und so ein stabiles, anfrageunabhängiges Wichtigkeitsmaß liefert.

HITS Hubs und Autoritäten

Innerhalb eines anfragefokussierten Untergraphen weist HITS jeder Seite einen Autoritätswert zu, der proportional zu den Hub-Werten der Seiten ist, die auf sie verlinken, und einen Hub-Wert, der proportional zu den Autoritätswerten der Seiten ist, auf die sie verlinkt, berechnet durch Iteration dieser sich gegenseitig verstärkenden Beziehungen bis zur Konvergenz.

Clinical relevance

PageRank war zentral für den Aufstieg der großflächigen Websuche und bleibt ein konzeptioneller Referenzpunkt für Wichtigkeit und Autorität in Graphen. Link-Analyse-Ideen verallgemeinern sich über das Web hinaus auf Zitationsnetzwerke, den Einfluss in sozialen Netzwerken, Betrugserkennung und Empfehlungssysteme, überall dort, wo empfehlungsähnliche Links Informationen tragen.

History

In den Jahren 1998 und 1999 zeigten zwei nahezu gleichzeitige Vorschläge, dass Hyperlinks Autorität kodieren: Kleinbergs HITS und Pages und Brins PageRank. Die anfrageunabhängigen, global berechneten Werte von PageRank erwiesen sich als gut geeignet für die Bereitstellung im Web-Maßstab und bildeten die Grundlage einer führenden Suchmaschine, während HITS die Forschung zur Themenextraktion und später zum Graph-Ranking beeinflusste.

Key figures

• Larry Page
• Sergey Brin
• Jon Kleinberg
• Rajeev Motwani

Seminal works

• page1999
• kleinberg1999
• brin1998

Frequently asked questions

Was ist der Unterschied zwischen PageRank und HITS?

PageRank berechnet im Voraus einen einzigen anfrageunabhängigen Wichtigkeitswert für jede Seite aus dem gesamten Webgraphen, während HITS anfrageabhängige Hub- und Autoritätswerte auf einem kleinen Untergraphen berechnet, der zur Abfragezeit um die Anfrage herum aufgebaut wird. PageRank lässt sich leichter auf die Web-Bereitstellung skalieren.

Warum benötigt PageRank einen Dämpfungsfaktor?

Ohne ihn könnte der zufällige Surfer in Seiten ohne ausgehende Links oder in Zyklen gefangen werden, und die stationäre Verteilung wäre möglicherweise nicht eindeutig oder wohldefiniert. Die Dämpfungs-(Teleportations-)Wahrscheinlichkeit ermöglicht es dem Surfer, gelegentlich zu einer zufälligen Seite zu springen, was einen eindeutigen, gutartigen Wert garantiert.