Upload
horst-gloeckner
View
214
Download
0
Embed Size (px)
Citation preview
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
1Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Vorlesung Sommersemester 2003
Algorithmische Grundlagen des Internets
XChristian Schindelhauer
HEINZ NIXDORF INSTITUTUniversität Paderborn
Fakultät für Elektrotechnik, Informatik und MathematikInstitut für Informatik
AG Theoretische InformatikAlgorithmen, Komplexitätstheorie, Paralleles Rechnen
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
2Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
ACHTUNGNeue Räume
Christian Schindelhauer•Raum:F2.315•Tel.: 60-6692
Klaus Volbert•Raum:F2.313•Tel.: 60-6722
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
3Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Webseitensuche
o PageRank [Brin&Page 98] Vergibt jeder Web-Seite einen absoluten Rang (rank)/Autorität Rang berücksichtigt Eingrad und Autorität des Eingrads Idee Seiten sind wichtig, wenn wichtige Seite auf sie zeigen
o HITS (HyperText Induces Topic Search) [Kleinberg 98] Ausgehend von einem Seitenstamm aus einer textuellen Suche Betracht Hubs (Hinweisseiten) und Autoritäten, Idee:
• Gute Hubs zeigen gute Autoritäten an• Gute Autoritäten werden von guten Hubs adressiert
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
4Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Vereinfachter PageRank-Algorithmus
o Vereinfachter PageRank-Algorithmus Rank einer Web-Seite R(u) [0,1] Wichtige Seiten vererben ihr Gewicht (gleichmäßig unter ihren
Nachfolgern)
c ist Normalisierungsfaktor, so dass ||R(u)||1=1 Vorgängermenge Bu
Nachfolgermenge Fu
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
5Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Vereinfachter PageRankBeispiel
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
6Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Matrixdarstellung
R c M R ,wobei R Vektor (R(1),R(2),… R(n)) und M folgende n n – Matrix ist:
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
7Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Vereinfachter PageRank-Algorithmus
o Konvergiert der vereinfachte PageRank-Algorithmus?
o Wieviele Lösungen gibt es?
o Wie sinnvoll sind diese?
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
8Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Eigenvektor als Fixpunkt der RekursionStochastische Matrix
o Für Vektor x, n n-Matrix und Zahl λ: Wenn M x = λ x , ist x Eigenvektor und λ Eigenwert
o Jede n n-Matrix M hat höchstens n Eigenwerteo Beobachtung:
Stochastische Matrizen beschreiben Markov-Prozesse über den Zustandsraum {1,..,n}
Prob[ij] = Mij
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
9Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Eigenvektor als Fixpunkt der RekursionStochastische Matrix
o Die L1-Norm eines Vektors ist gegeben als
Eigenwerte von M |i| 1
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
10Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
PeriodizitätBeispiel 1
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
11Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
PeriodizitätBeispiel 2
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
12Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Notwendige Bedingung für Periodizität
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
13Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Hinreichende Bedingung für Konvergenz
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
14Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Hinreichende Bedingung für Konvergenz
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
15Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Hinreichende Bedingung für Konvergenz
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
16Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Nachteile des vereinfachten PageRank-Algorithmus
o Web-Graph hat Senken, d.h. Seiten ohne Links M ist keine stochastische Matrix
o Web-Graph ist periodisch Konvergenz unmöglich
o Web-Graph ist nicht stark zusammenhängend Verschiedene Konvergenzvektoren möglich
o Rang-Senken: Sarke Zusammenhangskompenenten ohne ausgehenden Kangen „saugen“ Gewicht der Vorgänger auf
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
17Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Lösung durch PageRank
o Prozess startet mit zufälliger Seiteo Jede Senke erhält Links auf jede Seite in Vo Nur mit Wahrscheinlichkeit q < 1 wird vereinfachter PageRank
durchgeführtAnsonsten starte mit zufälliger Startseite
o M ist stochastisch!
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
18Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
PageRank-Algorithmus
o Graph der Matrix besteht aus einer starken Zus.-komponente
o Rundwege der Länge 1 existieren
PageRank konvergiert gegen den eindeutigen Eigenvektor mit Eigenwert 1
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
19Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Kleinbergs HITS-Algoirhtmus(HyperText Induced Search)
o Anwendung: Textuelle Suche führt zu großen Anzahl von Treffern, z.B.
• Suche nach „windows“ Gewünschte Seite enthält nicht Suchwort
• z.B. http://www.porsche.com enthält weder „Sportwagen“ noch „Auto“
Suche nach allgemeinen Begriffeno Idee des Algorithmus
Autorität/Relevanz einer Web-Seite wird durch Links auf Hinweisseiten (hubs) bezeugt
• z.B. Eisenbahnfans sammeln Links von Eisenbahngesellschaften
Autoritäten weisen auf die Qualität von Hinweisseiten hin Ähnlicher Mechanismus wie PageRank-Algorithmus
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
20Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Basismengenauswahl
o Ideal: S ist relativ klein S enthält viele relevante
Web-Seiten S enthält die meisten
(oder viele) der wichtigstenAutoritäten
o Knotenheuristik Erweitere um Nachfolger
•da Hinweisseiten in R auf diese zeigen
Erweitere um max. d Vorgänger•um ausreichende Anzahl von Hinweisseiten zu erhalten
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
21Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Kantenmengenheuristik
o Neben Knoten werden Kanten eingeschränkt:
o Kantenmengenheuristik Lösche interne Links (innerhalb der selben Domain)
• wegen Navigationslinks• wegen Links auf Autor
Erlaube maximal m ( 4-8) Links aus gleicher Domain auf eine Seite
• wegen Werbelinks• wegen Links auf Softwaretool
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
22Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Gegenseitige Verstärkung
o Gewichtung für Autorität einer Seite i: xi
o Gewichtung für Hinweiseigenschaft einer Seite i: yi
o Autorität/Relevanz einer Web-Seite wird durch Links auf Hinweisseiten (hubs) bezeugt
o Autoritäten weisen auf die Qualität von Hinweisseiten hin
c1, c2 normieren x und y bezüglich der L2-Norm:
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
23Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Der HITS-Algorithmus
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
24Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Matrixdarstellung
o Aus Adjazenzmatrix:
o Autoritäten:
o Hinweisseiten:
o Nach t Iterationen:
o D.h.
HEINZ NIXDORF INSTITUTUniversität Paderborn
EIM ‒ Institut für Informatik
25Algorithm. Grundlagen des Internets7. Juli 2003
Christian Schindelhauer
Matrixdarstellungo M = A AT ist symmetrische Matrix
o Für symmetrische Matrizen sind alle n Eigenwerte reell sind die n Eigenvektoren orthogonal
o Es existiert die Darstellung
o wobei für die Spaltenvektoren Si gilt
o Falls größter Eigenwert 1 > 2 konvergiert der HITS-Algorithmus