HEINZ NIXDORF INSTITUT Universität Paderborn EIM Institut für Informatik 1 Algorithm. Grundlagen des Internets 30. Juni 2003 Christian Schindelhauer Vorlesung

HEINZ NIXDORF INSTITUTUniversität Paderborn

EIM ‒ Institut für Informatik

1Algorithm. Grundlagen des Internets30. Juni 2003

Christian Schindelhauer

Vorlesung Sommersemester 2003

Algorithmische Grundlagen des Internets

IXChristian Schindelhauer

[email protected]


Fakultät für Elektrotechnik, Informatik und MathematikInstitut für Informatik

AG Theoretische InformatikAlgorithmen, Komplexitätstheorie, Paralleles Rechnen





Überblick Suchmaschinenhttp://www.searchengineshowdown.com/

(Stand Dez. 2002)

o Gespeicherte Dokumentmenge:

Search EngineShowdown

Estimate (millions)

Claim (millions)

Google 3,033 3,083

AlltheWeb 2,106 2,116

AltaVista 1,689 1,000

WiseNut 1,453 1,500

Hotbot 1,147 3,000

MSN Search 1,018 3,000

Teoma 1,015 500

NLResearch 733 125

Gigablast 275 150





Webseitensuche

o Moderne Websuchalgorithmen verlassen sich nicht nur auf textuelle Suche: Problem des Überflusses an Trefferseiten

• 10.000 Wörter decken 95% jedes Texts ab (Paretoverteilung)

• Mehr Web-Seiten als Wörter

Gesucht: wichtige Seiten, d.h. Seiten mit Autorität Wichtige Seiten enthalten nicht den Suchbegriff

• http://www.porsche.com: weder Sportwagen oder Auto

• http://www.airbus.com: weder Aircraft noch Airjet

• http://www.google.de/ weder Search engine noch Suchmaschine

Bestimmte Seiten besitzen fast alle Schlüsselwörter• http://wortschatz.uni-leipzig.de/top10000en.txt

Web-Verzeichnisse, Z.B. www.yahoo.com, www.web.de, www.netscape.com

• enthalten viele Begriffe, aber keine Autoritäten für ein Gebiet Namensgebung der URL irreführend:

• http://www.haus.com/ ist Webverzeichnis

Bestimmte Suchbegriffe fast überall z.B. WWW, Web, windows, java





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





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





Vereinfachter PageRankBeispiel





Matrixdarstellung

R c M R ,wobei R Vektor (R(1),R(2),… R(n)) und M folgende n n – Matrix ist:





Vereinfachter PageRank-Algorithmus

o Konvergiert der vereinfachte PageRank-Algorithmus?

o Wieviele Lösungen gibt es?

o Wie sinnvoll sind diese?





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 Eigenwerte

o Beobachtung:

Stochastische Matrizen beschreiben Markov-Prozesse über den Zustandsraum {1,..,n}

Prob[ij] = Mij





Eigenvektor als Fixpunkt der RekursionStochastische Matrix

o Die L1-Norm eines Vektors ist gegeben als

Eigenwerte von M |i| 1





PeriodizitätBeispiel 1





PeriodizitätBeispiel 2





Notwendige Bedingung für Periodizität





Hinreichende Bedingung für Konvergenz





Hinreichende Bedingung für Konvergenz





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





Lösung durch PageRank

o Prozess startet mit zufälliger Seite

o Jede Senke erhält Links auf jede Seite in V

o Nur mit Wahrscheinlichkeit q < 1 wird vereinfachter PageRank durchgeführtAnsonsten starte mit zufälliger Startseite

o M ist stochastisch!





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

Documents

HEINZ NIXDORF INSTITUT Universität Paderborn EIM Institut für Informatik 1 Algorithm. Grundlagen des Internets 30. Juni 2003 Christian Schindelhauer Vorlesung