Wie Google funktioniert

Ursprüngliche Autorin ist Christiane Rousseau. (Übersetzt ins Deutsche von Reinhild Kokula, Universität Würzburg)

Schon von Anfang an war Google „die“ Suchmaschine. Der Grund dafür ist die Überlegenheit seines Rangfolgenalgorithmus: der PageRank Algorithmus. Wegen der enormen Menge an Seiten im World-Wide-Web enden viele Suchanfragen tatsächlich mit Tausenden oder Millionen von Ergebnissen. Wenn diese nicht richtig geordnet sind, ist die Suche vielleicht gar keine Hilfe, weil man keine Millionen Einträge erkunden kann.

Wie funktioniert der PageRank Algorithmus?
Dies werden wir klären. Doch lassen Sie uns zunächst eine Suche mit Google starten. Am 4. Juni 2010 erhält man 16.300.000 Ergebnisse für Klein project, obwohl das Projekt gerade erst begonnen hat. An genau diesem Tag ist das erste Ergebnis

http://www.mathunion.org/icmi/other-activities/klein-project/introduction/
und nicht

http://www.kleinproject.org/
Die erste URL ist die URL einer Seite, die sich auf der Internetseite der International Mathematical Union befindet: http://www.mathunion.org.
Weil die International Mathematical Union eine wichtige Gesellschaft ist, erscheint ihre offizielle Internetseite als erstes Ergebnis, wenn man die Suchanfrage „International Mathematical Union“ startet. Weiterhin kommuniziert sie die Wichtigkeit all ihrer Seiten, von welchen eine

http://www.mathunion.org/icmi/other-activities/klein-project/introduction/ ist. Ein paar Monate oder Jahre später könnten wir erwarten, dass die Seite

http://www.kleinproject.org/
als erstes Ergebnis für die Suche Klein project erscheint.

Um den Algorithmus zu erklären, modellieren wir das Internet als einen orientierten Graphen. Die Knoten sind die Seiten und die orientierten Kanten sind die Links zwischen Seiten. Wie gerade erklärt entspricht jede Seite einer anderen URL. Somit kann jede Webseite mehrere Seiten enthalten. Im Modell gibt es keinen Unterschied zwischen den einzelnen Unterseiten einer Webseite und der Titelseite, allerdings wird der Algorithmus mit großer Wahrscheinlichkeit die Titelseite einer wichtigen Webseite höher platzieren.

Ein einfaches Beispiel

Betrachten wir das obige einfache Netz, das die fünf Seiten $A$ , $B$ , $C$ , $D$ und $E$ beschreibt. Dieses Netz enthält wenige Links. Wenn wir auf Seite $A$ sind, dann gibt es nur einen Link zu Seite $B$ . Doch wenn man auf Seite $C$ ist, findet man drei Links und kann wählen, ob man zu Seite $A$ , $B$ oder $E$ fortfahren möchte. Beachten Sie, dass es mindestens einen Link von jeder Seite aus gibt.

Spielen wir ein Spiel, das lediglich ein zufälliger Spaziergang auf dem orientierten Graphen ist. Bei Beginn an einer Seite wählen wir bei jedem Schritt einen beliebigen Link von der Seite, auf der wir gerade sind, und folgen ihm. Wenn man in diesem Beispiel o.B.d.A. auf der Seite $B$ beginnen, so können wir zu $A$ oder zu $C$ gehen, wobei jeder Fall eine Wahrscheinlichkeit von $1/2$ aufweist. Wenn wir jedoch auf $D$ beginnen, so sind wir gezwungen, mit einer Wahrscheinlichkeit von $1$ nach $A$ zu gehen. Wir wiederholen das Spiel.

Wo werden wir nach $n$ Schritten sein?Um diesen Prozess zu automatisieren, repräsentieren wir das Netz durch die folgende Matrix $P$ , in der jede Spalte einen Startpunkt repräsentiert und jede Zeile die Seite, auf der wir ankommen.

$P=\begin{matrix} \begin{matrix} A & B & C & D & E \end{matrix} & \\ \left(\ \ \begin{matrix} 0 & \frac12 & \frac13 & 1 & 0 \\ 1 & 0 & \frac13 & 0 & \frac13 \\ 0 & \frac12 & 0 & 0 & \frac13 \\ 0 & 0 & 0 & 0 & \frac13 \\ 0 & 0 & \frac13 & 0 & 0 \end{matrix} \ \ \right) & \begin{matrix} A \\ B\\ C\\ D\\ E\end{matrix} \end{matrix}$

Wir weisen darauf hin, dass die Summe der Einträge jeder Spalte gleich $1$ ist und dass alle Einträge größer oder gleich $0$ sind. Matrizen mit diesen zwei Eigenschaften sind besondere Matrizen: Jede solche Matrix ist die Matrix eines Markow-Ketten-Prozesses und heißt deswegen die Markow-Übergangsmatrix. Sie besitzt immer $1$ als Eigenwert und es gibt einen Eigenvektor zum Eigenwert $1$ , dessen Komponenten alle kleiner gleich $1$ und größer gleich $0$ sind, wobei ihre Summe $1$ ergibt. Doch bevor wir uns die Definition von Eigenwert und Eigenvektor ins Gedächtnis rufen erkunden wir die Vorteile der Matrixrepräsentation des Netzgraphs.

Betrachten wir eine zufällige Variable $X_n$ mit Werten in der Menge der Seiten $\{A,B,C,D, E\}$ , die $N$ viele Seiten enthält (hier $N=5$ ). $X_n$ repräsentiert die Seite, auf der wir nach n Schritten des zufälligen Spaziergangs gelandet sind. Wenn wir $p_{ij}$ den Eintrag der Matrix $P$ nennen, der sich in der $i$ -ten Zeile und $j$ -ten Spalte befindet, so ist folglich pij die bedingte Wahrscheinlichkeit, dass wir im $(n+1)$ -ten Schritt auf der i-ten Seite landen, wenn wir im $n$ -ten Schritt auf der $j$ -ten Seite sind:

$p_{ij}=\text{Prob}(X_{n+1}= i\mid X_n=j).$

Beachten Sie, dass diese Wahrscheinlichkeit unabhängig von $n$ ist! Wir sagen, dass ein Markow-Kettenprozess keine Erinnerung an die Vergangenheit hat. Man sieht leicht, dass die Wahrscheinlichkeiten nach zwei Schritten in der Matrix $P^2$ summiert werden können.

Beweisen wir dies (wenn Sie wollen, können Sie den Beweis überspringen). Das Gesetz der totalen Wahrscheinlichkeit ergibt

$\text{Prob}(X_{n+2}=i \mid X_n=j)=\sum_{k=1}^N\text{Prob}(X_{n+2}= i \;\text{and}\; X_{n+1}=k \mid X_n=j).$

Nach Definition der bedingten Wahrscheinlichkeit gilt

$\text{Prob}(X_{n+2}=i \mid X_n=j)=\sum_{k=1}^N\frac{\text{Prob}(X_{n+2}= i \;\text{and}\; X_{n+1}=k \;\text{and}\; X_n=j)} {\text{Prob}(X_n=j)}.$

Wir nutzen einen altbekannten Trick und multiplizieren und dividieren mit derselben Menge:

$\begin{multline*} \text{Prob}(X_{n+2}=i \mid X_n=j)=\\ \sum_{k=1}^N\frac{\text{Prob}(X_{n+2}= i \;\text{and}\; X_{n+1}=k \;\text{and}\; X_n=j)} {\text{Prob}(X_{n+1}=k \;\text{and}\; X_n=j)}\frac{\text{Prob}(X_{n+1}=k \;\text{and} \; X_n=j)}{\text{Prob}(X_n=j)}. \end{multline*}$

Der erste Quotient ist gleich

$\text{Prob}(X_{n+2}= i | X_{n+1}=k \;\text{and}\; X_n=j)= \text{Prob}(X_{n+2}= i | X_{n+1}=k ),$

weil der Markow-Kettenprozess keine Erinnerung vor dem vorherigen Schritt hat. Daher gilt

$\begin{align*}\text{Prob}(X_{n+2}=i \mid X_n=j)&=\sum_{k=1}^N\text{Prob}(X_{n+2}= i \mid X_{n+1}=k) \text{Prob}(X_{n+1}=k \mid X_n=j) \\ &=\sum_{k=1}^N p_{ik}p_{kj} \\ &=(P^2)_{ij}. \end{align*}$

In unserem Beispiel folgt

$P^2=\begin{matrix} \begin{matrix} A & B & C & D & E \end{matrix} & \\ \left(\ \ \begin{matrix}\frac12 & \frac16 & \frac16 & 0 & \frac{11}{18} \\ 0 & \frac23 & \frac49 & 1 & \frac19 \\ \frac12 & 0 & \frac5{18} & 0 & \frac16 \\ 0 & 0 & \frac19 & 0 & 0 \\ 0 & \frac16 & 0 & 0 & \frac19 \end{matrix} \ \ \right) & \begin{matrix} A \\ B\\ C\\ D\\ E\end{matrix} \end{matrix}$

Wenn man diese Idee wiederholt, wird klar, dass der Eintrag $(P^m)_{ij}$ der Matrix $P^m$ die Wahrscheinlichkeit $\text{Prob}(X_{n+m}=i\mid X_n=j)$ beschreibt. Zum Beispiel:

$P^{32} =\begin{matrix} \begin{matrix} \:\:A \quad& \:\:B\quad & \:\:C \quad& \:\:D\quad &\:\: E \quad\end{matrix} & \\ \left(\ \ \begin{matrix} 0.293 & 0.293 & 0.293 & 0.293 & 0.293 \\ 0.390 & 0.390 & 0.390 & 0.390 & 0.390 \\ 0.220 & 0.220 & 0.220 & 0.220 & 0.220 \\ 0.024 & 0.024 & 0.024 & 0.024 & 0.024 \\ 0.073 & 0.073 & 0.073 & 0.073 & 0.073 \end{matrix} \ \ \right) & \begin{matrix} A \\ B\\ C\\ D\\ E\end{matrix}\end{matrix}$

Alle Spalten von $P^{32}$ sind identisch, wenn wir die Genauigkeit auf 3 Dezimalen festsetzen, und sie sind dieselben wie die Spalten von Pn, wenn $n>32$ ist. Wenn wir eine höhere Genauigkeit wählen, so findet man auch eine Stabilisierung, aber für $n$ größer als $32$ . Daher ist nach $n$ Schritten, sofern $n$ ausreichend groß ist, die Wahrscheinlichkeit, auf einer Seite zu sein, unabhängig von der Startposition!

Betrachten wir zudem den Vektor

$\pi^t=(0.293,0.390,0.220,0.024,0.073)$

( $\pi$ ist ein vertikaler Vektor und seine Transposition $\pi^t$ ist ein horizontaler Vektor). Man kann leicht zeigen, dass $P\pi= \pi$ . Wenn wir die $i$ -te Koordinate des Vektors $\pi^t$ als die Wahrscheinlichkeit setzen, auf der Seite $i$ zu einer gegebenen Zeit $n$ zu sein, und somit die Wahrscheinlichkeitsverteilung der Seiten zum Zeitpunkt $n$ ist, so ist sie auch die Wahrscheinlichkeitsverteilung zum Zeitpunkt $n+1$ . Aus diesem Grund wird der Vektor $\pi$ auch als stabile Verteilung bezeichnet. Diese stabile Verteilung erlaubt es, die Seiten zu ordnen. In unserem Beispiel ordnen wir die Seiten als $B$ , $A$ , $C$ , $E$ , $D$ und bestimmen $B$ als die wichtigste Seite.

Der allgemeine Fall

Der allgemeine Fall kann genau wie unser Beispiel behandelt werden. Wir stellen das Netz als einen orientierten Graphen dar, in dem die $N$ Knoten die $N$ Seiten des Netzes repräsentieren und die orientierten Kanten die Links zwischen den Seiten sind. Wir fassen den Graphen in einer N $N\times N$ -Matrix zusammen, $P$ , wobei die $j$ -Spalte die $j$ -te Startseite beschreibt und die $i$ -Zeile die $i$ -te Zielseite. In unserem Beispiel haben wir einen Vektor gefunden, der erfüllt. Dieser Vektor ist ein Eigenvektor zum Eigenwert $1$ . Rufen wir uns die Definition von Eigenwert und Eigenvektor in den Sinn.

Definition. Sei P eine N x N-Matrix. Eine Zahl $\lambda\in \mathbb C$ ist ein Eigenwert von $P$ , falls es einen nichttrivialen Vektor $X\in \mathbb C^N$ gibt, sodass $PX=\lambda X$ . Einen solchen Vektor $X$ nennt man einen Eigenvektor von $P$ .

Wir erinnern uns ebenfalls an die Methode zur Ermittlung von Eigenwerten und Eigenvektoren.

Proposition Sei $P$ Eine $N\times N$ Matrix. Die Eigenwerte von $P$ sind die Wurzeln des charakteristischen Poynoms $\det(\lambda I- P)=0$ , wobei $I$ die $N\times N$ -Einheitsmatrix ist. Die Eigenvektoren zu einem Eigenwert $\lambda$ sind die nichttrivialen Lösungen des homogenen linearen Gleichungssystems $(\lambda I - P)X=0$ .

Der folgende tiefergehende Satz von Frobenius garantiert, dass wir für eine mit einem Netzgraphen verknüpfte Matrix immer eine feste Lösung finden.

Satz (Satz von Frobenius) Wir betrachten eine $N\times N$ Markow-Übergangsmatrix $P=(p_{ij})$ (wobei $p_{ij}\in [0,1]$ für alle $i,j$ , und die Summe der Einträge jeder Spalte gleich $1$ ist, also $\sum_{i=1}^Np_{ij}=1$ ).
Dann gilt:

$\lambda=1$ ist ein Eigenwert von $P$ .
Für jeden Eigenwert $\lambda$ von P gilt $|\lambda|\leq 1$ .
Es gibt einen Eigenvektor $\pi$ zum Eigenwert $1$ , dessen Koordinaten alle größer oder gleich Null sind. O.B.d.A. können wir annehmen, dass die Summe seiner Koordinaten $1$ ist.

Nun ist es Zeit, die Stärke dieses Satzes zu bewundern. Aus diesem Grund werden wir die vereinfachte Hypothese stellen, dass die Matrix $P$ eine Basis $\mathcal{B}=\{v_1, \dots , v_n\}$ an Eigenvektoren hat und wir nehmen an, dass $v_1$ der Vektor $\pi$ des Satzes von Frobenius ist. Für jedes $v_i$ existiert ein $\lambda_i$ derart, dass $Pv_i=\lambda_iv_i$ . Betrachten wir einen beliebigen nichttrivialen Vektor $X$ mit $X^t= (x_1, \dots, x_N)$ , wobei $x_i\in[0,1]$ und $\sum_{i=1}^N x_i=1$ . Wir zerlegen $X$ in die Basis $\mathcal{B}$ :

$X=\sum_{i=1}^N a_iv_i.$

Ein technischer Beweis, den wir überspringen werden, erlaubt es zu zeigen, dass $a_1=1$ . Berechnen wir nun $PX$ :

$PX= \sum_{i=1}^Na_i Pv_i= \sum_{i=1}^n a_i\lambda_iv_i,$

Da $v_i$ ein Eigenvektor zum Eigenwert $\lambda_i$ ist. Und bei Iteration erhalten wir

$P^nX= \sum_{i=1}^n a_i\lambda_i^nv_i.$

Falls alle $\lambda_i$ für $i>1$ die Bedingung $|\lambda|<1$ erfüllen, dann gilt

$\lim_{n\to \infty} P^nX = a_1v_1=\pi.$

Genau das passiert in unserem Beispiel!

Beachten Sie jedoch, dass der Satz nicht garantiert, dass eine beliebige Matrix $P$ , die die Hypothese des Satzes erfüllt, diese Eigenschaft aufweisen wird. Beschreiben wir die möglichen Symptome und das Gegenmittel.

Mögliche Symptome.

Der Eigenwert $1$ kann eine mehrfache Wurzel des charakteristischen Polynoms $\det(\lambda I -A)=0$ sein.
Die Matrix $P$ kann andere Eigenwerte $\lambda$ haben als $1$ , die mit Modulo gleich $1$ sind.

Was tun wir in diesem Fall?

Wir nennen eine Markow-Übergangsmatrix ohne Symptome eine reguläre Markow-Übergangsmatrix, nämlich:

Definition. Eine Markow-Übergangsmatrix ist regulär, falls

Der Eigenwert $1$ eine einfache Wurzel des charakteristischen Polynoms $\det(\lambda I -A)=0$ ist.
Alle anderen Eigenwerte $\lambda$ von $P$ außer $1$ haben Modulos kleiner als $1$ . Bedenken Sie, dass die meisten Matrizen $P$ regulär sind. Wenn also die Markow-Übergangsmatrix eines Netzes nicht regulär ist, so lautet die Strategie, die Matrix leicht umzuformen, sodass sie regulär wird.

Gegenmittel. Wir betrachten die $N\times N$ Matrix $Q= (q_{ij})$ mit $q_{ij} = \frac1N$ für alle $i, j$ . Wir ersetzen die Matrix $P$ des Netzes mit der Matrix

(1) $\begin{equation*}P_\beta= (1-\beta) P+ \beta Q, \end{equation*}$

für kleine $\beta\in [0,1]$ (der Wert $\beta= 0.15$ wird von Google benutzt). Bedenken Sie, dass die Matrix $P_\beta$ noch nichtnegative Einträge besitzt und dass die Summe der Einträge jeder Spalte immer noch gleich $1$ ist, wodurch es noch eine Markow-Übergangsmatrix ist. Der folgende Satz sichert, dass ein solches $\beta$ existiert, für das wir die Symptome kuriert haben.

Satz Für eine beliebige Markow-Übergangsmatrix $P$ gibt es immer ein beliebig kleines, positives $\beta$ , sodass die Matrix $P_\beta$ regulär ist. Sei $\pi$ der Eigenvektor von $1$ zur Matrix normiert, sodass die Summe seiner Koordinaten 1 sei. Für die Matrix und einen nichttrivialen Vektor $X$ , wobei $X^t= (p_1, \dots, p_N)$ mit $p_i\in[0,1]$ und $\sum_{i=1}^N p_i=1$ , gilt

(2) $\begin{equation*}\lim_{n\to \infty} (P_\beta)^nX= \pi.\end{equation*}$

Zusammenhang zum Banachschen Fixpunktsatz

Eine andere (anstehende) Vignette behandelt den Banachschen Fixpunktsatz. Der obige Satz kann als Spezialisierung dessen angesehen werden. Sie können diesen Teil überspringen, wenn Sie die andere Vignette nicht gelesen haben. In der Tat gilt:
Satz Sei $P$ eine reguläre Markow-Transformationsmatrix. Betrachten wir $\mathcal{S}=\{X\mid X^t=(p_1, \dots p_N), p_i\in [0,1],\sum_{i=1}^N p_i=1\}$ , mit angemessenem Abstand $d(X,Y)$ zwischen den Punkten (dieser Abstand ist abhängig von $P$ ). Auf $\mathcal{S}$ betrachten wir den linearen Operator $L: \mathcal{S} \rightarrow \mathcal{S}$ , definiert durch $L(X)=PX$ . Der Operator $L$ ist eine Kontraktion auf $\mathcal{S}$ und es existiert ein $c\in [0,1[$ , sodass für alle $X,Y\in \mathcal{S}$ gilt

$d(L(X),L(Y)) \leq c\,d(X,Y).$

Dann existiert ein eindeutiger Vektor $\pi\in \mathcal{S}$ derart, dass $L(\pi)=\pi$ .

Zudem können wir anhand eines beliebigen gegebenen $X_0\in \mathcal{S}$ die Folge $\{X_n\}$ durch Induktion definieren, wobei $X_{n+1} = L(X_n)$ . Dann gilt $\lim_{n\to \infty} X_n=\pi$ .

Definition des Abstands $d$ . Die Definition des Abstands $d$ ist recht geschickt und kann übersprungen werden. Hier wird er nur der Vollständigkeit zuliebe eingefügt und für den Leser, der auf die Details drängt. Wir beschränken uns auf den Fall, in dem die Matrix $P$ diagonalisierbar ist. Sei $\mathcal{B}=\{v_1=\pi, v_2, \dots, v_N\}$ eine Basis aus Eigenvektoren. Vektoren $X,Y\in\mathcal{S}$ können mithilfe der Basis $\mathcal{B}$ geschrieben werden:

$X=\sum_{i=1}^N a_iv_i, \quad Y=\sum_{i=1}^N b_iv_i,$

Wobei $a_i,b_i\in \mathbb C$ . Dann definieren wir

$d(X,Y)=\sum_{i=1}^n |a_i-b_i|.$

Mit diesem Anstand ist $\mathcal{S}$ ein abgeschlossener metrischer Raum, was bedeutet, dass alle Cauchyfolgen konvergieren.

Dieser Satz sichert nicht nur die Existenz eines $\pi$ , sondern liefert eine Methode, um es als den Grenzwert der Folge $\{X_n\}$ zu konstruieren. Wir haben eine Illustration dieser Konvergenz in unserem Beispiel gesehen. Tatsächlich ist die $j$ -te Spalte von $P^n$ der Vektor $P^n e_j$ , wobei $e_j^t= (0,\dots, 0, 1, 0, \dots,0)$ der $j$ -te Vektor der kanonischen Basis ist. In unserem Beispiel hätten wir den Vektor $\pi$ auch direkt finden können durch Lösung des Systems $(I-P)X=0$ mit der Matrix

$I-P= \left(\begin{matrix} 1 &- \frac12 & -\frac13 & -1 & 0 \\ -1 & 1 & -\frac13 & 0 & -\frac13 \\ 0 & -\frac12 & 1 & 0 & -\frac13 \\ 0 & 0 & 0 & 1 & -\frac13 \\ 0 & 0 & -\frac13 & 0 & 1 \end{matrix}\right).$

Wir hätten herausgefunden, dass alle Lösungen der Form $(4s, \frac{16}3s,3s,\frac13 s,s)^t$ sind für $s\in\mathbb R$ . Die Lösung, deren Summe der Koordinaten $1$ ergibt, ist folglich $\pi$ mit

$\pi^t=\left(\frac{12}{41}, \frac{16}{41}, \frac{9}{41}, \frac1{41}, \frac{3}{41}\right).$

Praktische Berechnung der festen Verteilung

Wir haben die einfache Idee identifiziert, die dem Algorithmus unterliegt. Allerdings ist es nicht so trivial, die feste Verteilung $\pi$ , also einen Eigenvektor zum Eigenwert $1$ für die Matrix $P_\beta$ in (1), zu finden, wenn die Matrix Milliarden Zeilen und Spalten hat: sowohl die Rechenzeit als auch der benötigte Speicherplatz erweisen sich als große Herausforderungen. Die normale Methode der Gauß-Elimination ist in diesem Fall unbrauchbar, wegen der Größe der Berechnung und weil man dabei durch kleine Koeffizienten teilen muss. Ein effektiverer Algorithmus nutzt die Eigenschaft (2) (siehe [LM]). Dies bildet den Zusammenhang zur bevorstehenden Vignette über den Banachschen Fixpunktsatz, die klarstellen wird, dass der Beweis des Banachschen Fixpunktsatzes einen Algorithmus liefert, um den Fixpunkt zu konstruieren.

Tatsächlich beginnen wir mit $X_0$ derart, dass

$X_0^t= (\frac1{N},\frac1{N}, \dots, \frac1{N}),$

und wir müssen $\lim_{n\to \infty} (P_\beta)^nX_0$ berechnen. Normalerweise liefert $P_\beta^nX_0$ für $n$ zwischen $50$ und $100$ eine relativ gute Approximation von $\pi$ . Durch Induktion berechnen wir $X_{n+1} =P_\beta X_n$ . Sogar solche Berechnungen sind recht lang. Tatsächlich hat die Matrix $P_\beta$ in (1) aufgrund der Berechnung keine Nulleinträge. Andererseits sind die meisten Einträge von $P$ gleich Null. Also müssen wir die Berechnung zerlegen um dies auszunutzen, nämlich durch

$X_{n+1} = (1-\beta)PX_n +\beta Q X_n.$

Aufgrund dieser speziellen Form von $Q$ prüft man leicht nach, dass $QX= X_0$ , wenn $X$ ein Vektor ist, deren Einträge summiert $1$ ergeben. Folglich genügt es, die folgende Folge zu berechnen:

$X_{n+1} = (1-\beta)PX_n +\beta X_0.$

Schlussfolgerung

Wir haben hiermit den öffentlichen Teil von Googles PageRank Algorithmus präsentiert. Man kann bereits mit einfachen Netzen experimentieren und das Ranking seiner eigenen Seite verbessern, indem man zusätzliche interne und externe Links an optimalen Stellen einfügt. Manche private kultiviertere Teile werden weiterhin entwickelt. Manche von ihnen bestehen daraus, die „neutrale“ Matrix Q aus (1) mit einer Matrix zu ersetzen, die den Geschmack des Internetsurfers reflektiert. Andere sichern, dass das Ranking nicht zu sehr sensibel auf Manipulationen reagiert, die von denjenigen vorgenommen werden, die das Ranking ihrer Seiten zu verbessern suchen.
Als generelle Schlussfolgerung können wir festhalten: Eine einfache, clevere Idee hat zu einem immensen Durchbruch in der Effizienz von Suchmaschinen geführt und zur Geburt eines kommerziellen Empires. Auch wenn die Implementation selbst eine rechenbetonte Tat ist, benötigte die zugrundeliegende Idee „elementare“ Mathematik, nämlich die lineare Algebra und die Wahrscheinlichkeitstheorie. Diese mathematischen Standardtools, vor allem die Diagonalisierung von Matrizen, konnten ihre volle Kraft entfalten, weil sie außerhalb ihres „normalen“ Kontexts genutzt wurden. Außerdem haben wir die vereinenden Ideen innerhalb der Wissenschaft hervorgehoben, mit denen der Banachsche Fixpunktsatz Anwendungen so weit entfernt seines Ursprungs findet.

Bibliographie

[E] M. Eisermann, Comment Google classe les pages webb, http://images.math.cnrs.fr/Comment-Google-classe-les-pages.html, 2009.

[LM] A. N. Langville and C. D. Meyer, A Survey of Eigenvector Methods
for Web Information Retrieval, SIAM Review, Volume 47, Issue 1,
(2005), pp. 135–161.

[RS] C. Rousseau and Y. Saint-Aubin, Mathematics and
technology, SUMAT Series, Springer-Verlag, 2008 (A French version of the book exists, published in the same series.)

Wie Google funktioniert

Related

Laisser un commentaire Annuler la réponse

Receive notice of every new vignette.

Search

Meta

Wie Google funktioniert

Partager :

Related

Laisser un commentaire Annuler la réponse

Receive notice of every new vignette.

Search

Meta