Hits Algorithmus

Hyperlink-induzierte Themensuche (Hits; auch bekannt als Hubs und Behörden) ist ein Verbindungsanalyse Algorithmus Das bewertet Webseiten, entwickelt von von Jon Kleinberg. Die Idee hinter Hubs und Behörden ergab sich aus einem bestimmten Einblick in die Erstellung von Webseiten, als sich das Internet ursprünglich bildete. Das heißt, bestimmte Webseiten, die als Hubs bezeichnet werden, dienten als große Verzeichnisse, die in den von ihnen gehaltenen Informationen nicht tatsächlich maßgeblich waren, sondern als Zusammenstellung eines breiten Informationskatalogs verwendet wurden, der Benutzer auf andere maßgebliche Seiten leiteten. Mit anderen Worten, ein guter Hub repräsentiert eine Seite, die auf viele andere Seiten hingewiesen hat, während eine gute Autorität eine Seite darstellt, die von vielen verschiedenen Hubs verknüpft ist.^[1]

Das Schema weist daher zwei Bewertungen für jede Seite zu: seine Behörde, die den Wert des Inhalts der Seite schätzt, und dessen Hub -Wert, der den Wert seiner Links zu anderen Seiten schätzt.

Geschichte

In Zeitschriften

Viele Methoden wurden verwendet, um die Bedeutung wissenschaftlicher Zeitschriften zu bewerten. Eine solche Methode ist Garfields Schlagfaktor. Zeitschriften wie Wissenschaft und Natur sind mit zahlreichen Zitaten gefüllt, sodass diese Magazine sehr hohe Auswirkungen auf Faktoren haben. Wenn Sie also zwei weitere obskure Zeitschriften vergleichen, die ungefähr die gleiche Anzahl von Zitaten erhalten haben, hat jedoch eine dieser Zeitschriften viele Zitate von erhalten Wissenschaft und NaturDiese Zeitschrift muss höher eingestuft werden. Mit anderen Worten, es ist besser, Zitate aus einem wichtigen Tagebuch zu erhalten als aus einem unwichtigen.^[2]

Im Internet

Dieses Phänomen tritt auch in der vor Internet. Das Zählen der Anzahl der Links zu einer Seite kann uns eine allgemeine Schätzung ihrer Bekanntheit im Web geben Yahoo!, Google, oder Msn. Weil diese Websites von sehr hoher Bedeutung sind, aber auch auch SuchmaschinenEine Seite kann viel höher als ihre tatsächliche Relevanz eingestuft werden.

Algorithmus

Erweiterung des Stammessatzes in einen Basissatz

Im Hits -Algorithmus besteht der erste Schritt darin, die relevantesten Seiten an der Suchabfrage abzurufen. Dieses Set heißt die Stammsatz und kann durch Aufnehmen der Top-Seiten erhalten werden, die von einem textbasierten Suchalgorithmus zurückgegeben werden. EIN Basiset wird generiert, indem der Stammsatz mit allen Webseiten, die daraus verknüpft sind, und einige der Seiten, die darauf verknüpft sind, erweitert werden. Die Webseiten im Basissatz und alle Hyperlinks zwischen diesen Seiten bilden einen fokussierten Untergraphen. Die Hits -Berechnung wird nur dazu durchgeführt fokussierter Untergraph. Laut Kleinberg besteht der Grund für den Bau eines Basissatzes darin, sicherzustellen, dass die meisten (oder viele) der stärksten Behörden enthalten sind.

Autoritäts- und Hub -Werte werden in einem gegenseitig definiert gegenseitige Rekursion. Ein Autoritätswert wird als Summe der skalierten Hub -Werte berechnet, die auf diese Seite hinweisen. Ein Hub -Wert ist die Summe der skalierten Autoritätswerte der Seiten, auf die er verweist. Einige Implementierungen berücksichtigen auch die Relevanz der verknüpften Seiten.

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

Autoritäts -Update: Aktualisieren Sie jeden Knoten Autoritätsbewertung gleich der Summe der Summe sein Hub Scores von jedem Knoten, der darauf hinweist. Das heißt, ein Knoten erhält eine hohe Autoritätsbewertung, indem sie von Seiten verknüpft werden, die als Hubs für Informationen anerkannt werden.
Hub -Update: Aktualisieren Sie jeden Knoten Hub -Score gleich der Summe der Summe sein Autoritätspunkte von jedem Knoten, auf den es zeigt. Das heißt, ein Knoten erhält einen hohen Hub -Score, indem sie mit Knoten, die als Behörden zu diesem Thema angesehen werden, verlinkt.

Der Hub -Score und die Autoritätsbewertung für einen Knoten werden mit dem folgenden Algorithmus berechnet:

Beginnen Sie mit jedem Knoten, der einen Hub -Score und eine Autoritätsbewertung von 1 hat.
Führen Sie die Behörde -Aktualisierungsregel aus
Führen Sie die Hub -Update -Regel aus
Normalisieren Sie die Werte, indem Sie jeden Hub -Score durch quadratische Wurzel der Summe der Quadrate aller Hub -Scores teilen und jede Autoritätsbewertung durch Quadratwurzel der Summe der Quadrate aller Autoritätswerte teilen.
Wiederholen Sie nach Bedarf aus dem zweiten Schritt.

Hits wie Buchseite und Brin's Seitenrang, ist ein iterativer Algorithmus basierend auf Verknüpfung der Dokumente im Web. Es hat jedoch einige große Unterschiede:

Es ist abhängig abhängig, dh die (Hubs and Authority) bewerteten, die sich aus der Verbindungsanalyse ergeben, werden von den Suchbegriffen beeinflusst.
Als Folge wird es zur Abfragezeit und nicht zum Indexierungszeit ausgeführt, wobei der zugehörige Treffer auf die Leistung mit der Abfragezeit begleitet wird.
Es wird häufig von Suchmaschinen verwendet. (Obwohl ein ähnlicher Algorithmus von von Teoma, was erworben wurde von Fragen Sie Jeeves/Ask.com.))
Es berechnet zwei Punkte pro Dokument, Hub und Autorität im Gegensatz zu einer einzigen Punktzahl.
Es wird auf einer kleinen Teilmenge von „relevanten“ Dokumenten (einem "fokussierten Untergraphen" oder Basissatz) verarbeitet, nicht alle Dokumente wie bei PageRank.

Im Detail

Um das Ranking zu beginnen, lassen wir uns ${\ displayStyle \ mathrm {auth} (p) = 1}$ und ${\ displayStyle \ mathrm {Hub} (p) = 1}$ Für jede Seite ${\ displayStyle p}$ . Wir berücksichtigen zwei Arten von Aktualisierungen: Behörde -Aktualisierungsregel und Hub -Update -Regel. Um die Hub-/Autoritätspunkte jedes Knotens zu berechnen, werden wiederholte Iterationen der Behörde -Aktualisierungsregel und der Hub -Update -Regel angewendet. Eine k-Schritt-Anwendung des Hub-Autoritäts-Algorithmus beinhaltet, dass die Behörde-Aktualisierungsregel und dann die Hub-Update-Regel beantragt werden.

Behörde -Aktualisierungsregel

Für jeden ${\ displayStyle p}$ Wir aktualisieren ${\ displayStyle \ mathrm {auth} (p)}$ zu $oder$ wo ${\ displayStyle p _ {\ mathrm {to}}}$ ist alle Seiten, die auf Seite verlinken ${\ displayStyle p}$ . Das heißt, die Autoritätsbewertung einer Seite ist die Summe aller Hub -Scores von Seiten, die darauf hinweisen.

Hub -Update -Regel

Für jeden ${\ displayStyle p}$ Wir aktualisieren ${\ displayStyle \ mathrm {Hub} (p)}$ zu $oder$ wo ${\ displayStyle p _ {\ mathrm {from}}}$ ist alle Seiten welche Seite ${\ displayStyle p}$ Links zu. Das heißt, der Hub -Score einer Seite ist die Summe aller Autoritätszahlen von Seiten, auf die sie verweist.

Normalisierung

Die endgültigen Hub-Authoritätswerte von Knoten werden nach unendlichen Wiederholungen des Algorithmus bestimmt. Als direkt und iterativ anwenden Sie die Hub -Aktualisierungsregel und die Behörde -Aktualisierungsregel zu divergierenden Werten, ist dies erforderlich normalisieren die Matrix nach jeder Iteration. Somit werden die aus diesem Prozess erhaltenen Werte letztendlich konvergieren.

Pseudocode

G: = Seiten von Seitenfür jeden Seite p in G tun  p.Auth = 1 // p.Auth ist die Autoritätsbewertung der Seite p  p.Hub = 1 // p.Hub ist der Hub -Score der Seite p zum Schritt aus 1 zu k tun // Führen Sie den Algorithmus für k Schritte Norm = 0 aus für jeden Seite p in G tun  // Aktualisieren Sie zuerst alle Autoritätswerte p.Auth = 0 für jeden Seite q in P. Incomingneighbors tun // P. Incomingneighbors ist der Satz von Seiten, auf die sich verknüpfen p  p.Auth += q.Hub norm += quadratisch (p.Auth) // Berechnen Sie die Summe der quadratischen Auth -Werte, um Norm = SQRT (Norm) zu normalisieren. für jeden Seite p in G tun  // Die Auth -Scores aktualisieren p.Auth = p.Auth / norm // Normalisieren Sie die Auth -Werte Norm = 0 für jeden Seite p in G tun  // dann alle Hub -Werte aktualisieren p.Hub = 0 für jeden Seite r in P.OUTUGYNEIGHBORS tun // P.OUTUGYNEIGHBORS ist der Satz von Seiten, die p Links zu p.Hub += r.Auth norm += quadratisch (p.Hub) // Berechnen Sie die Summe der quadratischen Hub -Werte, um Norm = SQRT (Norm) zu normalisieren. für jeden Seite p in G tun  // dann alle Hub -Werte aktualisieren p.Hub = p.hub / norm // Normalisieren Sie die Hub -Werte

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, einschränken muss. Eine Möglichkeit, dies zu umgehen Quadratwurzel der Summe der Quadrate aller Hub -Werte. Dies ist, was der obige Pseudocode.

Nicht konvergierende Pseudocode

G: = Seiten von Seitenfür jeden Seite p in G tun  p.Auth = 1 // p.Auth ist die Autoritätsbewertung der Seite p  p.Hub = 1 // p.Hub ist der Hub -Score der Seite p Funktion Hubsandaauthorities (G)) zum Schritt aus 1 zu k tun // Führen Sie den Algorithmus für k -Schritte aus für jeden Seite p in G tun  // Aktualisieren Sie zuerst alle Autoritätswerte p.Auth = 0 für jeden Seite q in P. Incomingneighbors tun // P. Incomingneighbors ist der Satz von Seiten, auf die sich verknüpfen p  p.Auth += q.Hub für jeden Seite p in G tun  // dann alle Hub -Werte aktualisieren p.Hub = 0 für jeden Seite r in P.OUTUGYNEIGHBORS tun // P.OUTUGYNEIGHBORS ist der Satz von Seiten, die p Links zu p.Hub += r.Auth

Siehe auch

Seitenrang

Verweise

^ Christopher D. Manning, Prabhakar Raghavan & Hinrich Schütze (2008). "Einführung zum Informationsabruf". Cambridge University Press. Abgerufen 2008-11-09.{{}}: CS1 Wartung: Verwendet Autorenparameter (Link)
^ Kleinberg, Jon (Dezember 1999). "Hubs, Behörden und Gemeinschaften". Cornell Universität. Abgerufen 2008-11-09.

Kleinberg, Jon (1999). "Autoritative Quellen in einer hyperlinkten Umgebung" (PDF). Journal of the ACM. 46 (5): 604–632. Citeseerx 10.1.1.54.8485. doi:10.1145/324133.324140.
Kleine.; Shang, Y.; Zhang, W. (2002). "Verbesserung von Hits-basierten Algorithmen in Webdokumenten". Proceedings der 11. International World Wide Web Conference (www 2002). Honolulu, hi. ISBN 978-1-880672-20-4.

Externe Links

US -Patent 6.112.202
Erstellen Sie eine Datensuchmaschine aus einer relationalen Datenbank Suchmaschine in C# basierend auf Treffern

[1] Christopher D. Manning, Prabhakar Raghavan & Hinrich Schütze (2008). "Einführung zum Informationsabruf". Cambridge University Press. Abgerufen 2008-11-09.{{}}: CS1 Wartung: Verwendet Autorenparameter (Link)

[2] Kleinberg, Jon (Dezember 1999). "Hubs, Behörden und Gemeinschaften". Cornell Universität. Abgerufen 2008-11-09.

[1]

[2]