Die Mathematik hinter Google

By | 28. Juli 2018

Sicher haben sich viele im Mathe-Unterricht immer wieder die Frage gestellt, wo man das Ganze den irgendwann einmal brauchen wird. Die Antwort der meisten Lehrer, das das wichtig für´s Leben sein soll hat wohl die wenigsten zufrieden gestellt.

Hier soll nun ein Beispiel vorgestellt werden, wozu Matrizen und Eigenwerte in Zusammenhang mit dem Internet und dem Thema Künstliche Intelligenz verwendet werden können.

Stellen wir uns folgende Frage: Wir haben eine Netzwerk bestehend aus 4 Web-Seiten die auf verschiedene Arten miteinander verlinked (siehe Bild) sein sollen.

Bild

Wir möchten nun wissen, welche der Web-Seiten die wichtigste Seite ist. Also die die uns eine Suchmaschine als erstes liefert. Das zählen der Links führt uns dabei sicher nicht zum Ziel. Wir müssen den Flow im Netzwerk betrachten, um so festzustellen auf welcher Seite die meisten Klicks landen.

Dazu stellt man sich einen virtuellen “Surfer” vor, der die ganze Zeit zufällig auf die Links auf den Web-Seiten klickt und so eine Art Landkarte zeichnet, welche Seiten am häufigsten besucht werden.

Um dieses Verhalten zu berechnen kann man auf die Matrizen-Rechnung zurückgreifen. Man stellt als erstes das Netzwerk in Form einer 4×4 Matrix auf, in dem man einfach von jeder der vier Web-Seiten A,B,C und D aufschreibt mit welcher Wahrscheinlichkeit man von einer Seite zur nächsten kommt.

Da man von A nur zur Web-Seite B kommt ist das die Wahrscheinlichkeit 1. Von B kommt man nach A aber auch nach C daher bekommen diese Verbindungen die Wahrscheinlichkeit 0.5 usw. SO erhält man eine Ausgangsmatrix M der folgenden Form:

Nun kann man leicht erkennen, wenn man die Matrizen-Multiplikation anwendet, dass eine Multiplikation genau einem simulierten Durchlauf des “Servers” entspricht und man dadurch eine veränderte Besuchs-Wahrscheinlichkeit erhält oder einen Wert für den Page Rank, wie er bei Google nach seinem Erfinder Lara Page genannt wird.

Wiederhalt man das mehrere Male so erhält man ein klares Bild, welche Seite mit welcher Wahrscheinlichkeit besucht wird und kann somit eine Aussage treffen, wo welche Information am ehesten zu finden sein wird. In unserem Beispiel ergibt sich nach 1000 Durchlaufen folgendes Bild:

Man erkennt das die Webseite B mit der höchsten Wahrscheinlichkeit aller Seiten angeklickt worden ist und kann somit eine klare Empfehlung abgeben.