Die Verwendung der Suchmaschine Google ist seit ihrer Veröffentlichung in den späten 1990er Jahren für einen Großteil der Internet-User Standard. Jede Art der Suche liefert die für den Benutzer relevanten Ergebnisse an den obersten Plätzen. Obwohl die mittlerweile zur Kulturtechnik („googeln“) avancierte Verwendung dieser Suchmaschine von Kindheitsalter an angewendet wird, ist eine tiefergehende Auseinandersetzung im Unterricht nach wie vor nicht Standard.
Spätestens seit dem großen Erfolg der Suchmaschine Google haben sich unzählige Artikel damit beschäftigt, wie der Suchalgorithmus von Google funktioniert. Um wissenschaftlich exakt zu bleiben, wird es dabei aber mathematisch sehr schnell kompliziert. Für die Beschreibung des PageRank-Algorithmus ist es notwendig, sich mit mehrstufigen Prozessen (Markov-Ketten), linearer Algebra (Übergangsmatrizen) und Analysis (Grenzwerte), auszukennen. In den dabei hergeleiteten Formeln wird dann (mathematisch exakt) das abstrakte mathematische Modell abgebildet. Genau diese Abstraktheit ist jedoch für Schüler der Sekundarstufe 1, und in der Regel auch für Schüler der Sekundarstufe 2, nicht fassbar.
Es wird hier darum versucht, die Funktionsweise der Suchmaschine Google mit möglichst wenig Mathematik, dafür aber mit einem gewissen Maß an Intuition, zu erklären. Trotzdem wird versucht, ein möglichst korrektes Modell des PageRank-Algorithmus zu beschreiben.
Inhaltsverzeichnis
1. Einleitung - Die grundlegende Frage
2. Modellbildung im Unterricht
2.1 Ergebnisveranschaulichung mittels Zahlenstrahl
2.2 Verfeinerung des Ergebnisses mittels Tabellenkalkulation
3. Intuitive Verfeinerung des Modells
3.1 Modellbildung mittels Markov-Kette – der Zufalls-Surfer
3.2 Der reale Zufalls-Surfer
3.3 Ein einfaches Beispiel?
4. Wie verläuft eine Anfrage bei Google
5. Abschließende Betrachtungen
Zielsetzung & Themen
Diese Arbeit hat zum Ziel, die Funktionsweise des PageRank-Algorithmus von Google für Schüler der Sekundarstufe 1 und 2 verständlich zu erklären, indem die komplexe mathematische Grundlage durch ein intuitives Modell ersetzt wird.
- Grundlagen der Google-Suchmaschinen-Logik
- Modellierung von Web-Strukturen durch gerichtete Graphen
- Veranschaulichung durch Zahlenstrahl-Methoden
- Iterative Berechnungsverfahren mittels Tabellenkalkulation
- Einführung in das Konzept des Random-Surfers und Markov-Ketten
Auszug aus dem Buch
Modellbildung mittels Markov-Kette – der Zufalls-Surfer
Das Beispiel aus Abbildung 2 wird nun mittels einer Markov-Kette erklärt. Das Ergebnis wird prinzipiell ident sein, allerdings ist die Erklärungsweise eine andere. Es geht darum, dass sich ein „Random-Walker“ zu bestimmten diskreten Zeitschritten mit einer bestimmten Wahrscheinlichkeit auf einer bestimmten Seite befindet.
Der Zufalls-Surfer befindet sich zum Zeitpunkt t=1 auf Seite A und damit auch mit einer Wahrscheinlichkeit von 1 auf Seite A (PA = 1). Im nächsten Schritt (t=2) befindet er sich jeweils mit einer Wahrscheinlichkeit P = 1/3 auf den Seiten B, C oder D (3 ausgehende Links von Seite A). Es gibt nun also eine Wahrscheinlichkeitsverteilung, mit der festgestellt werden kann, mit welcher Wahrscheinlichkeit sich der Zufallssurfer zum Zeitpunkt t=2 auf welcher Seite befindet. Zum Zeitpunkt t=3 werden dann wiederum die Teilwahrscheinlichkeiten entsprechend der ausgehenden Links verteilt:
Seite B hat 2 ausgehende Links zu C und D, somit wird die Wahrscheinlichkeit von Zeitpunkt t=2 jeweils zur Hälfte auf die Seiten C und D aufgeteilt.
Seite C hat einen ausgehenden Link zu Seite A. Die Wahrscheinlichkeit von Zeitpunkt t=2 wird somit zur Gänze auf Seite A übertragen.
Seite D hat 2 ausgehende Links zu A und C, somit wird die Wahrscheinlichkeit von Zeitpunkt t=2 jeweils zur Hälfte auf die Seiten A und C aufgeteilt.
Zusammenfassung der Kapitel
1. Einleitung - Die grundlegende Frage: Einführung in das Thema Suchmaschinen und die Problemstellung, wie Google die Relevanz von Webseiten trotz fehlender mathematischer Vorkenntnisse verständlich modelliert werden kann.
2. Modellbildung im Unterricht: Entwicklung eines ersten Wichtigkeitsmodells basierend auf eingehenden Links und deren Veranschaulichung mittels Zahlenstrahl sowie iterativer Berechnung.
3. Intuitive Verfeinerung des Modells: Erweiterung des Modells durch Markov-Ketten und das Konzept des "Zufalls-Surfers", um ein stabileres Ranking-Ergebnis zu erzielen.
4. Wie verläuft eine Anfrage bei Google: Erläuterung der praktischen Anwendung des vorberechneten Rankings bei einer tatsächlichen Benutzeranfrage.
5. Abschließende Betrachtungen: Zusammenfassung der Bedeutung von Suchmaschinen und der Zielsetzung der Arbeit, komplexe Algorithmen bildungsgerecht aufzubereiten.
Schlüsselwörter
Google, PageRank, Suchalgorithmus, Web-Struktur, Markov-Ketten, Zufalls-Surfer, Random-Walker, Linkstruktur, Backlinks, Modellbildung, Sekundarstufe, Informatikunterricht, Iteration, Dämpfungsfaktor, Teleportation
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit erklärt die Funktionsweise des Google PageRank-Algorithmus auf einem Niveau, das auch ohne tiefgreifende mathematische Vorkenntnisse für Schüler der Sekundarstufen 1 und 2 zugänglich ist.
Was sind die zentralen Themenfelder der Arbeit?
Die zentralen Felder umfassen die mathematische Modellierung von Webseiten-Strukturen, die Funktionsweise von Suchmaschinen-Rankings und die didaktische Aufbereitung von Algorithmen.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Ziel ist es, ein fachwissenschaftlich korrektes Modell des PageRank-Algorithmus zu beschreiben, das durch Intuition statt durch komplexe lineare Algebra fassbar gemacht wird.
Welche wissenschaftliche Methode wird verwendet?
Es werden iterative mathematische Verfahren, graphbasierte Darstellungen (gerichtete Graphen) und die Theorie der Markov-Ketten zur Modellierung des Surfer-Verhaltens eingesetzt.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil behandelt die grafische Darstellung durch Zahlenstrahlen, die Berechnung mittels Tabellenkalkulation sowie die theoretische Verfeinerung durch das Random-Surfer-Modell.
Welche Schlüsselwörter charakterisieren die Arbeit?
Schlüsselwörter sind unter anderem PageRank, Suchalgorithmus, Markov-Ketten, Random-Surfer und Linkstruktur.
Warum reicht das einfache Zählen von Backlinks nicht aus?
Einfache Linkzählungen können durch Linkfarmen manipuliert werden, weshalb eine Wichtung der verweisenden Seiten selbst notwendig ist.
Was genau ist der "Dämpfungsfaktor" d?
Der Dämpfungsfaktor (meist 0,85) repräsentiert die Wahrscheinlichkeit, dass ein Internet-Surfer einen Link ignoriert und stattdessen zufällig auf eine beliebige andere Seite springt.
Wie gehen die Autoren mit "Dangling Links" um?
Dangling Links, also Seiten ohne ausgehende Verweise, führen zu einem "Versickern" der Wichtung; die Arbeit schlägt vor, diese für die Berechnung aus dem Modell zu entfernen.
- Arbeit zitieren
- Dipl. Ing. Georg Sitter (Autor:in), 2016, Erklärung des PageRank-Algorithmus von Google ohne mathematische Vorkenntnisse, München, GRIN Verlag, https://www.grin.com/document/351590
