PageRank vs. HITS - kontext.fraunhofer.dekontext.fraunhofer.de/haenelt/kurs/Referate/SchmidtUlf... · Hyperlinked Induced Topic Search • HITS = Hyperlinked Induced Topic Search

Google PageRank vs. HITSGoogle PageRank vs. HITS

Seminar Information RetrievalSeminar Information Retrieval

Ulf SchmidtUlf Schmidt

ÜbersichtÜbersicht

• Einführung

• Hyperlinked Induced Topic Search

• Google PageRank

• Vergleich

• Weiterentwicklungen

• Fazit

• Quellen

29/01/07 Information Retrieval 2

EinführungEinführung

• Link-basierte Ranking Strategien: automatische Beurteilung von Webseiten anhand ihrer Linkstruktur

• Ziel beider Verfahren ist die Relevanzbeurteilung

• Idee: durch die Hyperlinkstruktur im WWW gibt es bereits eine indirekte Bewertung von Web-Seiten

→ Setzen eines Links stellt eine Empfehlung dar


Hyperlinked Induced Topic SearchHyperlinked Induced Topic Search

• HITS = Hyperlinked Induced Topic Search• von Jon Kleinberg an der Cornell University entwickelt (1997)• zum ersten Mal in der Suchmaschine "Clever" von IBM eingesetzt

• Suchtechnik, die die Struktur von Hyperlinks von Webseiten berücksichtigt

• Abschätzung der Autorität der Webseiten→ indem eine Webseite A einen Hyperlink auf eine Webseite B setzt, wird Seite B ein gewisses Maß an Autorität zugewiesen

• die Qualität der eingehenden Links wird bei der Relevanzermittlung berücksichtigt

• Unterscheidung von Hubs und Authorities


HITS HITS -- Hubs und AuthoritiesHubs und Authorities

• Authorities: Seiten mit hoher Autorität → viele eingehende (wichtige) Links (relevante Seite zu einem Thema)

• Hubs: Seiten mit hohen Anzahl von Verweisen auf Authorities (Seiten die Links zu einem bestimmten Thema sammeln)

• Hubs fassen thematisch relevante Authorities zusammen

• Hubs sind beispielsweise populäre Linksammlungen

• Authorities sind Seiten, die von Hubs oft verlinkt werden


HITS HITS -- Hubs und AuthoritiesHubs und Authorities

• guter Hub verweist zu vielen guten Authorities• Authority: eine Seite auf die von vielen guten Hubs

verwiesen wird→ Hubs und Authorities verstärken sich gegenseitig

• zusammengehörige Hubs und Authorities werden als Communities bezeichnet


HITS HITS -- BerechnungBerechnung

• Festlegung des Root Set (bestehend aus k Seiten) durch Eingeben eines Suchbegriffs in eine allgemeine Suchmaschine

• Erweiterung des Root Sets zur Basismenge (Base)

• Besteht aus allen Seiten des Root Sets, Seiten die in und aus dem Root Set verweisen

• Verwendung eines Höchstwertes für Anzahl Seiten die eingebracht werden, um Base klein zuhalten

• Bildung des Graphen, der durch die Basismenge induziert wird und entfernen aller internen Links (Navigationslinks)


HITS HITS -- AlgorithmusAlgorithmus

• jeder Seite i (aus der Menge i = 1…n Seiten) wird ein Hub-Gewicht hi und ein Authority-Gewicht ai zugeordnet

• A = Verlinkungsmatrix, wobei gilt:Ai,j = 1, falls Seite i einen Link auf Seite j besitzt undAi,j = 0, falls dies nicht der Fall

• AT = die Transponierte Matrix von A:

• Hub-Wert einer Seite i: Summe aller Authority-Werte der Seiten, die von i verlinkt sind

• Authority-Wert einer Seite i: Summe aller Hub-Werte der Seiten, die auf i verlinken


HITS HITS -- Algorithmus IIAlgorithmus II

• gegenseitiges Einsetzen der Definitionen:

• die Werte für a und h ergeben sich als Eigenvektoren der Matrizen AAT bzw. ATA


HITS HITS -- ProblemeProbleme

• HITS Algorithmus identifiziert die dichteste Community aus der Basismenge

• Es können unterschiedliche Communities auftreten:– Suchbegriff besitzt verschiedene Bedeutungen

(z.B.: Puma)– Suchbegriff nicht eindeutig einer Communities

zuordbar – Suchbegriff mit polarisierenden Communities

(z.B.: Abtreibung → Gegner und Befürworter verlinken ihre Seiten nicht miteinander)


HITS HITS -- ZusammenfassungZusammenfassung

• berücksichtigt die Semantik der Suchanfragen (im Gegensatz zu PageRank)

• Ergebnisqualität mindestens gleich hoch, wie bei derVerwendung von PageRank

• Ergebnismenge kann auch relevante Dokumente beinhalten, die keineTerme der Suchanfragen enthalten

• semantisch „unkorrekte“ Links, verfälschen das Ergebnis


Google PageRankGoogle PageRank

• von Lawrence Page und Sergey Brin (Google-Gründer)• großer Anteil an Googles Erfolg (Qualität der Ergebnisse)• Im Verlauf der Jahre natürlich reichlich Modifikationen und

Verbesserungen → hier nur ursprünglichen PageRank-Algorithmus

• Anfrage-unabhängiges Ranking der Seiten in einem Graph• nicht nur Vorkommen eines Suchbegriffs in einer Webseite wichtig,

sondern auch Anzahl der eingehenden Links für eine Webseite• Links von wichtigeren Seiten sind wertvoller als Links von weniger

wichtigen Seiten (Link von Yahoo ist mehr wert als von normaler Website)→ PageRank berechnet die Wichtigkeit aus der Linkstruktur

• Webseite um so wichtiger, je häufiger von anderen verlinkt und je wichtiger diese verlinkenden Seiten

• Rekursivität → Linkstruktur des gesamten WWWs


Google PageRank Google PageRank -- ArchitekturArchitektur

• PageRank ist unabhängig von der Anfrage oder den Textinhalten• PageRank jeder Seite wird vorausberechnet und gespeichert

• Berechnung des PageRanks für das komplette WWW laut Page/Brin ca. 100 Iterationen des Algorithmus notwendig(nur näherungsweise Berechnung da Web verdammt groß)

• genaue Details der Implementation sind nicht dokumentiert• Fakten hier basieren auf den frühen Veröffentlichungen


• anzeigbar in der Google Toolbar (Plugin für IE und Firefox), zeigt skalierten Rank auf Skala zwischen 0 und 10 an

Google PageRank Google PageRank -- ArchitekturArchitektur

• 3 Faktoren bei Umsetzung des PageRanks in Google:– Seitenspezifische Faktoren

(Textinhalt, Title-Tag, URL, …)– Ankertext eingehender Links

(Aktualität, Position, Hervorhebung, ...)– PageRank-Wert

• Kombination durch Multiplikation• bei Anfragen aus mehreren Begriffen PageRank nicht so

große Bedeutung


Google PageRank Google PageRank -- AlgorithmusAlgorithmus

• PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

PR(A) - PageRank einer Seite APR(Ti) - PageRank der Seiten Ti, von denen ein Link

auf die Seite A zeigtC(Ti) - Gesamtanzahl der Links auf Seite Tid - Dämpfungsfaktor (zwischen 0 und 1)


• PageRank der Seite A bestimmt sich rekursiv aus dem PageRank der Seiten die auf A verlinken

• PageRank der Seiten Ti fließt nicht gleichmäßig in den PageRank von Seite A ein (Gewichtung durch Anzahl C(T) der Links)

→ je mehr ausgehende Links Seite T hat, desto weniger PageRank an Seite A

Google PageRank Google PageRank -- Algorithmus IIAlgorithmus II

• Summe wird mit Dämpfungsfaktor d multipliziert• Minderung des Ausmaßes der Weitergabe des PageRanks• Modell zur Abbildung von Benutzer-Verhalten• Wahrscheinlichkeit welchen Link Surfer nimmt, ergibt sich

aus wievielen Links er die Auswahl hat


Google PageRank Google PageRank -- BeispielBeispiel


AA

BB CC

Dämpfungsfaktor d ist 0,5(Standardwert 0.85)

PR(A) = 14/13 = 1.07692308PR(B) = 10/13 = 0.76923077PR(C) = 15/13 = 1.15384615

• Summe der PageRanks aller Seiten gleich drei → Anzahl der Seiten

• da PageRank Erwartungswert für den Besuch einer Seite

• Für 3 Seiten lösbar, für WWW (Milliarden von Seiten) Gleichungssystem nicht lösbar

PR(A) = 0.5 + 0.5 PR(C)PR(B) = 0.5 + 0.5 (PR(A) / 2)PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))

Google PageRank Google PageRank -- Beispiel IIBeispiel II


AA

BB CC

DDXX

• PageRank von 1 für jede Seite• Seite X mit PageRank 10• Dämpfungsfaktor bei 0,5

Effekt eingehender Links

PR(A) = 0.5 + 0.5 (PR(X) + PR(D))= 5.5 + 0.5 PR(D)

PR(B) = 0.5 + 0.5 PR(A)PR(C) = 0.5 + 0.5 PR(B)PR(D) = 0.5 + 0.5 PR(C)

PR(A) = 19/3 = 6.33PR(B) = 11/3 = 3.67PR(C) = 7/3 = 2.33PR(D) = 5/3 = 1.67

• der Effekt des zusätzlichen Links auf Seite A setzt sich über die Verlinkung fort

→ Grad der Weitergabe von PageRank ist abhängig vom Dämpfungsfaktor

Google PageRank Google PageRank -- Beispiel IIBeispiel II


AA

BB CC

DDXX

• PageRank von 1 für jede Seite• Seite X mit PageRank 10

Effekt eingehender Links • bei d = 0,75:

PR(A) = 419/35 = 11.97PR(B) = 323/35 = 9.23PR(C) = 251/35 = 7.17PR(D) = 197/35 = 5.63

• wesentlich höhere PageRanks und gleichmäßiger verteilt

→ je höher der Dämpfungsfaktor um so höher dieser Effekt

• Summe der PageRanks von 14 auf 34

• Effekt so groß da auf ein geschlossenes System verlinkt wird (Wahrscheinlichkeit das die anderen Links verfolgt werden sehr groß)

→ nicht viele eingehende Links wichtig, sondern Link(s) mit hohem PageRank

Google PageRank Google PageRank -- Beispiel IIIBeispiel III


AA

BB

CC

• PageRank von 1 für jede Seite• Externer Link von A auf C• Dämpfungsfaktor bei 0,75

Effekt ausgehender Links

PR(A) = 14/23PR(B) = 11/23→ Summe 1. Site = 25/23

PR(C) = 35/23PR(D) = 32/23→ Summe 2. Site = 67/23

• aufsummierter PageRank beider Sites: 92/23 = 4 → bleibt erhalten

• Hinzufügen von Links hat keinen Einfluss auf den aufsummierten PageRank des Webs

DD

PR(A) = 0.25 + 0.75 PR(B)PR(B) = 0.25 + 0.375 PR(A)PR(C) = 0.25 + 0.75 PR(D) + 0.375 PR(A)PR(D) = 0.25 + 0.75 PR(C)

Google PageRank Google PageRank -- ProblemeProbleme

• Dangling Links:– manche Seiten haben keine ausgehenden Links→ PageRank bleibt stecken…

– Seiten können sich gegenseitig verlinken (Schleifen können entstehen)

– Schleifen sind Sammelbecken für Rank-Werte

– daher: Dangling Links werden bei der Berechnung entfernt und wenn Berechnung aller anderen Links fertig, deren Wert berechnet


Google PageRank Google PageRank -- ZusammenfassungZusammenfassung

• der Effekt eingehender Links ist am größten• jeder eingehender Link auf eine Webseite erhöht deren

PageRank• eine Webseite, die einen zusätzlichen eingehenden Link erhält,

erhöht nun auch den PageRank auf eventuell verlinkende Seiten (wird weitergegeben)

• aufaddierter PageRank aller Seiten des Webs gleich der Anzahl der Seiten

• besondere Gewichtung einzelner Seiten / bezahlte Links• bei Bestrafung von Websites: PageRank gleich 0• sind nicht vollkommen aus dem Index entfernt, erscheinen aber

in Suchergebnissen ganz unten und somit praktisch nicht auffindbar


VergleichVergleich

• PageRank Vorteile– Berechnungszeit ist sehr gering (bereits vorherberechnet)– HITS berechnet alles erst nach der Eingabe– weniger anfällig für Spam Links– hoher Berechnungsaufwand– nur Authorities werden berechnet

• HITS Vorteile– HITS Ranking beachtet auch die Anfrage– HITS berechnet Hubs und Authorities– einfach zur berechnen– schwierig in Echtzeit


WeiterentwicklungenWeiterentwicklungen

• ARC-Verfahren (Automatic Resource Compilation)– Erweiterung von HITS– der thematische Bezug von Links wird besser einbezogen– Links werden mit einem Gewicht bewertet

• TrustRank– Weiterentwicklung von PageRank– Zur Bekämpfung von Suchmaschinen-Spam– Faktoren: Alter der Domain, Änderungshäufigkeit, SERP Tracking

(Dauer auf Webseite)


FazitFazit

• Googles PageRank: Bestimmung des Ansehens aller Seiten im Web

• HITS: Bestimmung von Hubs und Authorities (Communities) eines Graphen von Webseiten

• basieren auf Linkanalyse

• Probleme: viele Links nur zur Navigation oder Werbung


QuellenQuellen

• Michael W. Berry and Murray Browne, Understanding Search Engines -Mathematical Modelling and Text Retrieval, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 2005, Pages 71-88

• Monica Bianchini, Marco Gori and Franco Scarselli, Inside PageRank, ACM Transactions on Internet Technology (TOIT), Volume 5, Issue 1, 2005, Pages 92 - 128

• Longzhuang Li, Yi Shang and Wei Zhang, Improvement of HITS-based Algorithms on Web Documents, Proceedings of the 11th international conference on World Wide Web, 2002, Pages 527 - 535

• Michael Brinkmeier, PageRank Revisited, ACM Transactions on Internet Technology (TOIT), Volume 6 , Issue 3, 2006, Pages 282 - 301

• Brian D. Davison, Overview: WWW Search Engines, 2003, http://www.cse.lehigh.edu/~brian/

• Rainer Kuhlen und Joachim Griesbaum, Information Retrieval - Suche im Internet - Suchdienste I: Kataloge und Suchmaschinen, 2003, http://www.inf-wiss.uni-konstanz.de/CURR/winter0203/IR/kursplan_ir_ws0203.html

• Wikipedia, Hubs und Authorities, 2006, http://de.wikipedia.org/wiki/Hubs_und_Authorities

• Theodora Tsikrika, Web Information Retrieval, 2002, http://qmir.dcs.qmul.ac.uk/teaching/2002/week11/lecture/

• Phil Craven, Google's PageRank Explained,http://www.webworkshop.net/pagerank.html


EndeEnde


Vielen Dank für Eure Aufmerksamkeit.