Erklärung des PageRank-Algorithmus von Google ohne mathematische Vorkenntnisse

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.

Einleitung - Die grundlegende Frage

Es gibt mittlerweile etliche Milliarden Webseiten. Dabei ist bemerkenswert, in welch kurzer Zeit Google Resultate für jede Art der Abfrage liefert. Noch bemerkenswerter ist es, dass zumeist auch noch auf den ersten 3 Plätzen jene Ergebnisse gelistet sind, die für den jeweiligen Suchenden am Relevantesten sind.

Welches Ergebnis wird ausgegeben, wenn auf Google nach „Michael Jackson“ gesucht wird [5]?

Als Resultat werden unzählige Webseiten, die sich mit dem Popstar Michael Jackson beschäftigen, angezeigt.

Solange über dieses Ergebnis nicht genauer nachgedacht wird, ist das Resultat sehr naheliegend. Allerdings ist zu bedenken, dass rund 170.000 „Jacksons“ im Telefonbuch der USA existieren, davon 3500 „Michael Jacksons“, wovon wiederum 55 auf den Gelben Seiten gelistet sind, also ein Unternehmen mit Webseite betreiben (Architekt, Anwalt, Ingenieur,…) [4]. Warum werden aber nicht diese Webseiten, sondern die Webseiten des Popstars auf den ersten Rängen angezeigt? Insgesamt gesehen ist das Ergebnis sicherlich passend, da die allermeisten Suchenden genau die Seiten des Popstars finden wollen. Aber warum weiß das Google zumeist so genau?

Es gibt bereits etliche Veröffentlichungen, die sich damit auseinandersetzen, wie Google bzw. Suchmaschinen im Hintergrund funktionieren. Hierbei sei beispielsweise auf [3], [BO], [7], [8] verwiesen. Der Unterschied zu den bereits veröffentlichten fachdidaktischen Arbeiten besteht vor allem darin, dass in dieser Arbeit versucht wird, bei fehlenden mathematischen Grundlagen, hier sei vor allem die Sekundarstufe 1 angesprochen, trotzdem ein fachwissenschaftlich korrektes Modell zu beschreiben.

Modellbildung im Unterricht

Die zugrundeliegende Idee der Google-Gründer liegt in der Bibliographie [2]. Hier wird die Wichtigkeit eines wissenschaftlichen Artikels daran gemessen, wie oft dieser Artikel in anderen Artikeln zitiert wird.

Das Internet ist ähnlich aufgebaut, wie Artikel und deren Zitate in der Bibliographie. Es besteht aus Seiten, die miteinander verbunden sind, sogenannten Links. Ein Link kann also adäquat zum Zitat als Empfehlung verstanden werden.

Eine erste Idee wäre es, analog zur Bibliographie, die Anzahl der eingehenden Links („Backlinks“) zu einer Webseite zu zählen. Eine Webseite mit einer besonders hohen (eingehenden) Linkanzahl wäre demnach sehr wichtig. Diese Methode wurde in der Realität auch vielfach angewendet. Mit sogenannten Linkfarmen wurden viele ausgehende Links erzeugt, welche auf bestimmte Webseiten verwiesen, die dann besonders wichtig werden sollten. Diese Methode darf jedoch nicht funktionieren, da ansonsten Seiten mit zweifelhafter Wichtigkeit sehr leicht wichtig gemacht werden könnten.

[Abbildungen werden in dieser Leseprobe nicht dargestellt. Bitte klicken sie auf das Cover für einen Blick ins Buch inklusive Abbildungen.]

Abbildung 1: Linkfarm - die Zielseite soll durch viele eingehende Links möglichst wichtig gemacht werden

Eine Lösung dieses Problems kann so sein, dass jede Seite eine Wichtigkeit hat und ihr Gewicht bei einem Verweis weitergibt. Die Linkfarm würde also ihr (vermutlich) geringes Gewicht durch die hohe Anzahl der ausgehenden Links in unzählige noch geringere Gewichte aufteilen, womit die Zielseiten keinen Gewinn in der Gewichtung mehr hätten.

Der Ansatz lautet also folgend: „Eine Seite ist dann wichtig, wenn viele wichtige Seiten auf sie verweisen“ [6].

Um diesen Ansatz nun zu veranschaulichen, wird ein Beispiel eines Mini-Internets, bestehend aus vier Seiten, aus [3], siehe Abbildung 2, herangezogen.

[Abbildungen werden in dieser Leseprobe nicht dargestellt. Bitte klicken sie auf das Cover für einen Blick ins Buch inklusive Abbildungen.]

Abbildung 2: Mini-Internet bestehend aus 4 Seiten

Mit der ersten Idee, also einfach die Anzahl der eingehenden Links zu zählen, wäre die resultierende Reihenfolge C vor A und D vor B, also C – (A – D) – B.

Um den Ansatz aus [6] korrekt durchzuführen, ist es notwendig auszuführen, das eine Seite mit einem ausgehenden Link ihr gesamtes Gewicht der anderen Seite überträgt. Hat eine Seite zwei ausgehende Links, so wird das Gewicht jeweils zur Hälfte an die Zielseiten übertragen, usw. . Eine Webseite mit ausgehenden Links gibt also ihre gesamte Wichtigkeit jeweils in gleichen Teilen an jene Seiten weiter, auf die sie verweist. In [6] wird auch noch festgelegt, dass mögliche Selbstverweise einer Seite auf sich selbst nicht in die Berechnung miteinbezogen werden. Dies würde bedeuten, dass sich eine Seite selbst wichtiger machen kann.

Es soll nun ein entsprechendes Modell entwickelt werden, um mathematisch korrekt vorzugehen.

Das Internet ist ein gerichteter Graph, wobei die Seiten den Knoten und die Links den gerichteten Kanten entsprechen. Es gibt n Seiten G_v , wobei v=1,..., n. Für jede Seite soll nun ein Wichtigkeitswert (PageRank) berechnet werden, PR(u) ,u=1,…, n. Der PageRank ist ein numerischer Wert, wenn nun PR(i)>PR(j), dann ist die Seite G_i wichtiger als die Seite G_j. ist die Anzahl der ausgehenden Links von der Webseite G_v,B_v die Menge der Seiten, die auf die Seite G_u verweisen. Die Bezeichnung „PageRank“ wurde ursprünglich bereits durch Sergey Brin und Larry Page [2] eingeführt.

Es ergibt sich folgendes Modell:

[Formeln werden in dieser Leseprobe nicht dargestellt. Bitte klicken sie auf das Cover für einen Blick ins Buch inklusive Formeln.]

Verständlicher kann erklärt werden:

Eine Seite G_u hat eingehende Links aus der MengeB_v. Über diese eingehenden Links erhält die SeiteG_u Gewichte. Jede Seite aus der Menge B_v gibt einen bestimmten Anteil des eigenen Gewichts an die Seite G_u weiter. Dieser Anteil errechnet sich aus dem Gewicht der Seite G_v durch die Anzahl der von der Seite G_v ausgehenden Links. Der PageRank einer Seite G_u ergibt sich dann aus der Summe der Gewichte der eingehenden Links. Die Werte der einzelnen PageRanks sind numerische Werte, damit kann eine Reihenfolge der Wichtigkeit der Webseiten erstellt werden.

Wie kann nun aber genau dieses mathematische Modell in der Sekundarstufe 1 erklärt werden, wenn die entsprechenden mathematischen Vorkenntnisse nicht vorhanden sind?

Ergebnisveranschaulichung mittels Zahlenstrahl

Basis für die Ergebnisveranschaulichung ist das Beispiel aus Abbildung 2. Jede der vier Seiten beginnt mit einer Wichtigkeit (PageRank) von 1. Für das Beispiel werden 4 Streifen mit jeweils 12 cm Länge benötigt, siehe Abbildung 3. Ein ganzer Streifen hat also den PageRank von 1.

[Abbildungen werden in dieser Leseprobe nicht dargestellt. Bitte klicken sie auf das Cover für einen Blick ins Buch inklusive Abbildungen.]

Abbildung 3: Veranschaulichung mittels Zahlenstrahlen

Schritt 1: Den einfachsten Beginn gibt es mit der Seite B. Diese hat einen eingehenden Link der Seite A, wobei die Seite A insgesamt 3 ausgehende Links besitzt. Der Zahlenstrahl von Seite A muss also gedrittelt werden und Seite B bekommt von Seite A ein Drittel dessen Gewichts (4cm). Auch die Seiten C und D erhalten jeweils ein Drittel des Gewichts von A. Dies ist in Abbildung 4 dargestellt.

[Abbildungen werden in dieser Leseprobe nicht dargestellt. Bitte klicken sie auf das Cover für einen Blick ins Buch inklusive Abbildungen.]

Abbildung 4: Veranschaulichung Schritt 1

…