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
29/01/07 Information Retrieval 3
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
29/01/07 Information Retrieval 4
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
29/01/07 Information Retrieval 5
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
29/01/07 Information Retrieval 6
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)
29/01/07 Information Retrieval 7
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
29/01/07 Information Retrieval 8
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
29/01/07 Information Retrieval 9
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)
29/01/07 Information Retrieval 10
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
29/01/07 Information Retrieval 11
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
29/01/07 Information Retrieval 12
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
29/01/07 Information Retrieval 13
• 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
29/01/07 Information Retrieval 14
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)
29/01/07 Information Retrieval 15
• 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
29/01/07 Information Retrieval 16
Google PageRank Google PageRank -- BeispielBeispiel
29/01/07 Information Retrieval 17
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
29/01/07 Information Retrieval 18
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
29/01/07 Information Retrieval 19
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
29/01/07 Information Retrieval 20
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
29/01/07 Information Retrieval 21
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
29/01/07 Information Retrieval 22
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
29/01/07 Information Retrieval 23
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)
29/01/07 Information Retrieval 24
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
29/01/07 Information Retrieval 25
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
29/01/07 Information Retrieval 26