HITS-Algorithmus – Wikipedia

Posted on by

Hyperlink-induzierte Themensuche (HITS; auch bekannt als Hubs und Behörden) ist ein von Jon Kleinberg entwickelter Linkanalysealgorithmus, der Webseiten bewertet. Die Idee hinter Hubs and Authorities entstand aus einer besonderen Einsicht in die Erstellung von Webseiten, als das Internet ursprünglich entstand; das heißt, bestimmte Webseiten, die als Hubs bekannt sind, dienten als große Verzeichnisse, die in Bezug auf die Informationen, die sie enthielten, nicht wirklich maßgeblich waren, sondern als Zusammenstellung eines breiten Informationskatalogs verwendet wurden, der Benutzer direkt zu anderen maßgeblichen Seiten führte. Mit anderen Worten, ein guter Hub stellt eine Seite dar, die auf viele andere Seiten verweist, während eine gute Autorität eine Seite darstellt, die von vielen verschiedenen Hubs verlinkt ist.[1]

Das Schema vergibt daher für jede Seite zwei Bewertungen: seine Autorität, die den Wert des Inhalts der Seite schätzt, und seinen Hub-Wert, der den Wert seiner Links zu anderen Seiten schätzt.

Geschichte[edit]

In Zeitschriften[edit]

Es wurden viele Methoden verwendet, um die Bedeutung wissenschaftlicher Zeitschriften einzustufen. Eine solche Methode ist der Impact-Faktor von Garfield. Zeitschriften wie Wissenschaft und Natur sind mit zahlreichen Zitaten gefüllt, wodurch diese Zeitschriften sehr hohe Impact-Faktoren haben. Wenn man also zwei eher obskure Zeitschriften vergleicht, die ungefähr die gleiche Anzahl von Zitaten erhalten haben, aber eine dieser Zeitschriften viele Zitate von Wissenschaft und Natur, muss diese Zeitschrift höher eingestuft werden. Mit anderen Worten, es ist besser, Zitate aus einer wichtigen Zeitschrift zu erhalten als aus einer unwichtigen.[2]

Im Internet[edit]

Dieses Phänomen tritt auch im Internet auf. Das Zählen der Links zu einer Seite kann uns eine allgemeine Einschätzung ihrer Bedeutung im Web geben, aber auch eine Seite mit sehr wenigen eingehenden Links kann auffallen, wenn zwei dieser Links von den Homepages von Websites wie Yahoo! stammen. Google oder MSN. Da diese Seiten von sehr hoher Bedeutung sind, aber auch Suchmaschinen sind, kann eine Seite viel höher gerankt werden als ihre tatsächliche Relevanz.

Algorithmus[edit]

Erweiterung der Wurzelmenge in eine Basismenge

Beim HITS-Algorithmus besteht der erste Schritt darin, die relevantesten Seiten für die Suchanfrage abzurufen. Dieses Set heißt die Wurzelsatz und kann erhalten werden, indem die von einem textbasierten Suchalgorithmus zurückgegebenen Top-Seiten verwendet werden. EIN Basisset wird generiert, indem das Root-Set mit allen Webseiten, die von ihm verlinkt sind, und einigen Seiten, die darauf verweisen, erweitert wird. Die Webseiten im Basissatz und alle Hyperlinks zwischen diesen Seiten bilden ein fokussiertes Unterdiagramm. Die HITS-Berechnung wird nur auf diesem durchgeführt fokussierter Untergraph. Laut Kleinberg besteht der Grund für die Konstruktion eines Basissatzes darin, sicherzustellen, dass die meisten (oder viele) der stärksten Autoritäten enthalten sind.

Autoritäts- und Hub-Werte werden in einer gegenseitigen Rekursion zueinander definiert. Ein Autoritätswert wird als Summe der skalierten Hubwerte berechnet, die auf diese Seite verweisen. Ein Hub-Wert ist die Summe der skalierten Autoritätswerte der Seiten, auf die er verweist. Einige Implementierungen berücksichtigen auch die Relevanz der verlinkten Seiten.

Der Algorithmus führt eine Reihe von Iterationen durch, die jeweils aus zwei grundlegenden Schritten bestehen:

  • Autoritätsupdate: Aktualisieren Sie die jedes Knotens Autoritätsbewertung gleich der Summe der Hub-Scores von jedem Knoten, der darauf zeigt. Das heißt, ein Knoten erhält eine hohe Autoritätsbewertung, indem er von Seiten verlinkt wird, die als Informations-Hubs erkannt werden.
  • Hub-Update: Aktualisieren Sie die jedes Knotens Hub-Score gleich der Summe der Autoritätsbewertungen von jedem Knoten, auf den es zeigt. Das heißt, einem Knoten wird eine hohe Hub-Punktzahl verliehen, indem er mit Knoten verknüpft wird, die als Autoritäten in diesem Bereich gelten.

Der Hub-Score und Authority-Score für einen Knoten wird mit dem folgenden Algorithmus berechnet:

  • Beginnen Sie damit, dass jeder Knoten einen Hub-Score und einen Autoritäts-Score von 1 hat.
  • Führen Sie die Autoritätsaktualisierungsregel aus
  • Führen Sie die Hub-Aktualisierungsregel aus
  • Normalisieren Sie die Werte, indem Sie jeden Hub-Score durch die Quadratwurzel der Summe der Quadrate aller Hub-Scores dividieren und jeden Authority-Score durch die Quadratwurzel der Summe der Quadrate aller Authority-Scores dividieren.
  • Ab dem zweiten Schritt nach Bedarf wiederholen.

HITS ist wie Page und Brins PageRank ein iterativer Algorithmus, der auf der Verknüpfung der Dokumente im Web basiert. Es gibt jedoch einige wesentliche Unterschiede:

  • Sie ist abfrageabhängig, dh die aus der Linkanalyse resultierenden (Hubs and Authority) Scores werden von den Suchbegriffen beeinflusst;
  • Als logische Folge wird es zur Abfragezeit und nicht zur Indexierungszeit mit dem zugehörigen Leistungseinbußen ausgeführt, das die Verarbeitung zur Abfragezeit begleitet.
  • Es wird nicht häufig von Suchmaschinen verwendet. (Obwohl ein ähnlicher Algorithmus von Teoma verwendet wurde, das von Ask Jeeves/Ask.com übernommen wurde.)
  • Es berechnet zwei Scores pro Dokument, Hub und Autorität, im Gegensatz zu einem einzelnen Score;
  • Es wird auf einer kleinen Teilmenge von “relevanten” Dokumenten (einem “fokussierten Untergraphen” oder Basissatz) verarbeitet, nicht auf allen Dokumenten, wie es bei PageRank der Fall war.

Im Detail[edit]

Um das Ranking zu beginnen, lassen wir

einduTh(P)=1{displaystyle mathrm {auth} (p)=1}

und

hduB(P)=1{displaystyle mathrm {hub} (p)=1}

für jede Seite

P{displaystyle p}

. Wir betrachten zwei Arten von Updates: Autoritätsaktualisierungsregel und Hub-Aktualisierungsregel. Um die Hub-/Autoritätsbewertungen jedes Knotens zu berechnen, werden wiederholte Iterationen der Autoritätsaktualisierungsregel und der Hubaktualisierungsregel angewendet. Eine k-stufige Anwendung des Hub-Autoritätsalgorithmus beinhaltet das k-malige Anwenden der Autoritätsaktualisierungsregel und dann der Hub-Aktualisierungsregel.

Autoritätsaktualisierungsregel[edit]

Für jeden

P{displaystyle p}

, wir aktualisieren

einduTh(P){displaystyle mathrm {auth} (p)}

zu

einduTh(P)=ΣQ∈PTÖhduB(Q){displaystyle mathrm {auth} (p)=displaystyle sum nolimits_{qin P_{mathrm {to}}}mathrm {hub} (q)}

wo

PTÖ{displaystyle P_{mathrm {to}}}

sind alle Seiten, die auf eine Seite verlinken

P{displaystyle p}

. Das heißt, die Autoritätsbewertung einer Seite ist die Summe aller Hub-Bewertungen der Seiten, die darauf verweisen.

Regel für Hub-Updates[edit]

Für jeden

P{displaystyle p}

, wir aktualisieren

hduB(P){displaystyle mathrm {Hub} (p)}

zu

hduB(P)=ΣQ∈PFRÖmeinduTh(Q){displaystyle mathrm {hub} (p)=displaystyle sum nolimits_{qin P_{mathrm {from}}}mathrm {auth} (q)}

wo

PFRÖm{displaystyle P_{mathrm {von} }}

ist alle seiten welche seite

P{displaystyle p}

Links zu. Das heißt, der Hub-Score einer Seite ist die Summe aller Autoritätsbewertungen der Seiten, auf die sie verweist.

Normalisierung[edit]

Die endgültigen Knotenwerte der Hub-Autorität werden nach unendlichen Wiederholungen des Algorithmus bestimmt. Da die direkte und iterative Anwendung der Hub Update Rule und Authority Update Rule zu abweichenden Werten führt, ist es notwendig, die Matrix nach jeder Iteration zu normalisieren. Somit werden die aus diesem Prozess erhaltenen Werte schließlich konvergieren.

Pseudocode[edit]

G := set of pages
for each page p in G do
    p.auth = 1 // p.auth is the authority score of the page p
    p.hub = 1 // p.hub is the hub score of the page p
for step from 1 to k do // run the algorithm for k steps
    norm = 0
    for each page p in G do  // update all authority values first
        p.auth = 0
        for each page q in p.incomingNeighbors do // p.incomingNeighbors is the set of pages that link to p
            p.auth += q.hub
        norm += square(p.auth) // calculate the sum of the squared auth values to normalise
    norm = sqrt(norm)
    for each page p in G do  // update the auth scores 
        p.auth = p.auth / norm  // normalise the auth values
    norm = 0
    for each page p in G do  // then update all hub values
        p.hub = 0
        for each page r in p.outgoingNeighbors do // p.outgoingNeighbors is the set of pages that p links to
            p.hub += r.auth
        norm += square(p.hub) // calculate the sum of the squared hub values to normalise
    norm = sqrt(norm)
    for each page p in G do  // then update all hub values
        p.hub = p.hub / norm   // normalise the hub values

Die Hub- und Autoritätswerte konvergieren im obigen Pseudocode.

Der folgende Code konvergiert nicht, da die Anzahl der Schritte, für die der Algorithmus ausgeführt wird, begrenzt werden muss. Eine Möglichkeit, dies zu umgehen, wäre jedoch, die Hub- und Autoritätswerte nach jedem “Schritt” zu normalisieren, indem jeder Autoritätswert durch die Quadratwurzel der Summe der Quadrate aller Autoritätswerte geteilt wird und jeder Hubwert durch die Quadratwurzel der Summe der Quadrate aller Hubwerte. Dies ist, was der obige Pseudocode tut.

Nicht konvergierender Pseudocode[edit]

G := set of pages
for each page p in G do
    p.auth = 1 // p.auth is the authority score of the page p
    p.hub = 1 // p.hub is the hub score of the page p

function HubsAndAuthorities(G)
    for step from 1 to k do // run the algorithm for k steps
        for each page p in G do  // update all authority values first
            p.auth = 0
            for each page q in p.incomingNeighbors do // p.incomingNeighbors is the set of pages that link to p
                p.auth += q.hub
        for each page p in G do  // then update all hub values
            p.hub = 0
            for each page r in p.outgoingNeighbors do // p.outgoingNeighbors is the set of pages that p links to
                p.hub += r.auth

Siehe auch[edit]

Verweise[edit]

Externe Links[edit]