aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/80-wahrscheinlichkeit/google.tex
blob: 314bea9f240db644d7c0ef644c80fd6911691b1b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
%
% google.tex -- Einstiegsproblem zur Behandlung von Google-Matrizen
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\section{Google-Matrix
\label{buch:section:google-matrix}}
\rhead{Google-Matrix}
Das Internet besteht aus einer grossen Zahl von Websites, etwa 1.7~Milliarden
aktiven Websites, jede besteht aus vielen einzelnen Seiten.
\index{Internet}%
Es ist daher angemessen von $N\approx 10^{10}$ verschiedenen Seiten auszugehen.
Eine natürliche Sprache umfasst dagegen nur einige 100000 bis Millionen
von Wörtern.
Ein durchschnittlicher Sprecher englischer Muttersprache verwendet nur etwa
50000 Wörter.
Die Zahl der Wörter, die auf den $N$ Seiten vorkommen können, ist also
viel kleiner als die Zahl der zur Verfügung stehenden Wörter.
Ein einzelnes Wort wird daher notwendigerweise auf einer grossen Zahl
von Seiten vorkommen.
Eine Suche nach einem bestimmten Wort wird in der überwiegenden Zahl
der Fälle derart viele Treffer zurückgeben, dass das Suchresultat
nur dann nützlich sein kann, wenn eine zusätzliche Informationsquelle
ermöglicht, die Treffer in eine sinnvolle Ordnung zu bringen.

Genau dieses Problem stellte sich den vielen traditionellen Suchmaschienen
in der ersten grossen Boomphase des Internets.
Traditionelle Information-Retrieval-Systeme operieren auf einem relativ
\index{Information-Retrieval}%
kleinen Dokumentbestand und gehen davon aus, dass bereits wenige, spezifische
Wörter nur in einem kleinen Teil des Dokumentbestandes vorkommen und damit
eine übersichtliche Treffermenge ergeben.
Die Einengung der Treffermenge mit der Suche nach einzelnen Wörtern
bedeutet aber auch, dass nach Synonymen oder alternative Formen eines
Wortes separat gesucht werden muss, was die Übersichtlichkeit wieder
zerstört.
\index{Treffermenge}%

%
% Ein Modell für Webseitenbesucher
%
\subsection{Ein Modell für Webseitenbesucher
\label{buch:subsection:modell-fuer-webseitenbesucher}}
\begin{figure}
\centering
\includegraphics{chapters/80-wahrscheinlichkeit/images/internet.pdf}
\caption{Modell-Internet als Beispiel für die Link-Matrix und die Google-Matrix.
\label{buch:figure:modellinternet}}
\end{figure}

Selbst das kombinierte Vorkommen von Wörtern oder Begriffen alleine reicht
nicht aus, um die Seiten zum Beispiel einem Fachgebiet zuzuordnen.
Dazu muss eine externe Informationsquelle angezapft werden.
Bei traditionellen Dokumenten liefert der Kontext, in dem ein
Dokument erfasst wurde, solche ergänzenden Informationen.
Eine Publikation in einem Fachjournal ordnet einen Text einem Fachgebiet zu.
Im World-Wide-Web liefert die Link-Struktur diesen Kontext.
\index{Link}%
Dokumente zu ähnlichen oder verwandten Themen werden bevorzugt
untereinander verlinkt sein.

Gesucht ist jetzt also ein Modell, welches objektiv die Linkstruktur
bewertet und daraus eine Rangordnung der Suchresultate ableitet.
Die Linkstruktur kann natürlich als gerichteter Graph betrachtet und 
mit Hilfe der Adjazenzmatrix~\eqref{buch:graphen:eqn:adjazenzmatrixgerichtet}
\index{Adjazenzmatrix}%
eines gerichteten Graphen beschrieben werden.
Dies trägt jedoch der Anzahl der Wahlmöglichkeiten nicht Rechnung.
Eine Website mit nur einem Link auf die Seite $j$ gibt der Seite $j$
mehr Gewicht als eine Seite mit vielen Links, unter denen der Link
auf die Seite $j$ einer von Vielen ist.
Im Beispiel-Internet der Abbildung~\ref{buch:figure:modellinternet}
signalisiert die Seite $6$ mit nur einem Link auf die Seite $8$
viel deutlicher, dass $8$ eine wichtige Seite ist, also dies die
Seite $5$ tut, die auch noch zwei andere Links enthält.
Wir können diesen Unterschied berücksichtigen, indem wir zu einem
Wahrscheinlichkeitsmodell übergehen, was wir im folgenden Abschnitt
tun werden.

%
% Wahrscheinlichkeitsinterpretation
%
\subsection{Wahrscheinlichkeitsinterpretation
\label{buch:subsection:wahrscheinlichkeitsinterpretation}}
Ein Internetbesucher kann eine grosse Zahl von Seiten besuchen.
In diesem Abschnitt soll ein Modell entwickelt werden, welches die
Wahrscheinlichkeit zu ermitteln gestattet, dass der Besucher auf
einer bestimmten Seite landet.

\subsubsection{Ereignisse und Wahrscheinlichkeiten}
Wir bezeichnen mit $S_i$ das Ereignis, dass sich der Besucher auf
der Seite mit der Nummer $i$ befindet, wobei $i=1,\dots,N$.
Gesucht ist die Wahrscheinlichkeit $P(S_i)$.
Ohne weitere Information müssen wir davon ausgehen, dass jede Seite
etwa gleich wahrscheinlich ist, dass also $P(S_i) = 1/N$.

Wir wissen jedoch mehr.
Wir wissen, dass der Besucher die verschiedenen Seiten zu einem guten 
Teil dadurch findet, dass er Links folgt.
Die Wahrscheinlichkeit $P(S_i)$ verändert sich also, wenn die Zahl der
Links ansteigt, die auf die Seite $i$ verweisen.
Zur Beschreibung dieses Phänomens brauchen wir die zusätzliche Ereignisse
$S_i'$, die mit Wahrscheinlichkeit $P(S'_i)$ eintreten, wenn sich der
Besucher nach Navigation entlang eines Links auf der Seite $i$ befindet.

Wir nehmen jetzt zusätzlich an, dass eine grosse Zahl von Besuchern über
lange Zeit ungefähr nach den gleichen Dingen suchen und sich daher
auf die gleiche Weise auf den verschiedenen Seiten verteilen und dass
insbesondere die Verteilung stationär ist, dass also $P(S_i) = P(S'_i)$
gilt.
\index{Suchmaschine}%
Suchmaschinen wie Google gehen davon aus, dass alle Besucher ungefähr
\index{Google}%
die gleichen Suchprioritäten haben, so dass es sich lohnt, die Suchresultate
nach der Wahrscheinlichkeit $P(S_i)$ zu ordnen und dem Suchenden die
wahrscheinlichsten Dokumente als erste zu zeigen.

\subsubsection{Bedingte Wahrscheinlichkeit}
Um einen Zusammenhang zwischen $P(S_i)$ und $P(S'_j)$ herzustellen, muss
die Navigation entlang der Links modelliert werden.
Die naheliegende Wahrscheinlichkeitsinterpretation ist die bedingte
Wahrscheinlichkeit $P(S'_j\mid S_i)$ dass der Besucher auf der Seite $j$
landet, nachdem er auf der Seite $i$ die Linknavigation verwendet hat.
Wenn es keinen Link zwischen den Seiten $i$ und $j$ gibt, dann ist diese
Navigation natürlich nicht möglich und es folgt $P(S'_j\mid S_i)=0$.
Falls es einen Link gibt, ist $P(S'_j\mid S_i)\ge 0$.

A priori wissen wir nicht, wie wahrscheinlich es ist, dass der Besucher
dem Link auf die Seite $j$ folgt, normalerweise werden nicht alle
Links mit gleicher Wahrscheinlichkeit verwendet.
Darüber haben wir aber keine Detailinformation.
Wir nehmen daher vereinfachend an, dass alle Links gleich wahrscheinlich
sind.
Enthält die Seite $i$ genau $n_i$ Links, dann ist die Wahrscheinlichkeit,
auf einer von $i$ aus verlinkten Seite $j$ zu landen, $P(S'_j\mid S_i) = 1/n_i$.

\subsubsection{Totale Wahrscheinlichkeit}
Der Satz von der totalen Wahrscheinlichkeit ermöglicht, einen Zusammenhang
\index{totale Wahrscheinlichkeit}%
\index{Wahrscheinlichkeit!totale}%
zwischen $P(S'_j)$ und $P(S_i)$ herzustellen.
Es gilt
\begin{equation}
P(S'_j)
=
P(S'_j\mid S_1) P(S_1)
+
P(S'_j\mid S_2) P(S_2)
+
\dots
+
P(S'_j\mid S_N) P(S_N)
=
\sum_{i=1}^N P(S_j'\mid S_i)P(S_i)
.
\label{buch:google:eqn:totalewahrscheinlichkeit}
\end{equation}
Dies kann in Matrix- und Vektorform übersichtlicher geschrieben werden.
Dazu fassen wir die Wahrscheinlichkeiten $p'_j=P(S'_j)$ und $p_i=P(S_i)$
also Vektoren
\[
p
=
\begin{pmatrix}
P(S_1)\\
P(S_2)\\
\vdots\\
P(S_N)
\end{pmatrix}
\qquad
\text{und}
\qquad
p'
=
\begin{pmatrix}
P(S'_1)\\
P(S'_2)\\
\vdots\\
P(S'_N)
\end{pmatrix}
\]
zusammen.
Die bedingten Wahrscheinlichkeiten $h_{ji}=P(S'_j\mid S_i)$ sind mit zwei Indizes
beschrieben, sie bilden daher in natürlicher Weise die sogenannte
{\em Link-Matrix}
\index{Link-Matrix}%
\begin{equation}
H
=
\begin{pmatrix}
P(S'_1\mid S_1)&P(S'_1\mid S_2)&\dots &P(S'_1\mid S_N)\\
P(S'_2\mid S_1)&P(S'_2\mid S_2)&\dots &P(S'_2\mid S_N)\\
\vdots     &\vdots     &\ddots&\vdots     \\
P(S'_N\mid S_1)&P(S'_N\mid S_2)&\dots &P(S'_N\mid S_N)
\end{pmatrix}.
\label{buch:google:eqn:linkmatrix}
\end{equation}
Die Formel~\eqref{buch:google:eqn:totalewahrscheinlichkeit} wird dann zur
Formel für das Produkt Matrix mal Vektor:
\[
(Hp)_j
=
\sum_{i=1}^N h_{ji} p_i
=
\sum_{i=1}^N P(S'_j\mid S_i) P(S_i)
=
p'_j
\qquad\Rightarrow\qquad
Hp=p'.
\]
Die Matrix $H$ modelliert also die Wahrscheinlichkeit der Navigation
entlang eines Links.

\begin{beispiel}
Für das Beispiel-Internet von Abbildung~\ref{buch:figure:modellinternet}
ist die zugehörige Link-Matrix
\begin{equation}
H =
\begin{pmatrix}
   0   & 0&   0   &   0   &   0   & 0&\frac12&   0   \\
\frac12& 0&\frac12&\frac13&   0   & 0&   0   &   0   \\
\frac12& 0&   0   &   0   &   0   & 0&   0   &   0   \\
   0   & 1&   0   &   0   &   0   & 0&   0   &   0   \\
   0   & 0&\frac12&\frac13&   0   & 0&   0   &   0   \\
   0   & 0&   0   &\frac13&\frac13& 0&   0   &\frac12\\
   0   & 0&   0   &   0   &\frac13& 0&   0   &\frac12\\
   0   & 0&   0   &   0   &\frac13& 1&\frac12&   0
\end{pmatrix}.
\label{buch:google:eqn:linkmatrixbeispiel}
\end{equation}
\qedhere
\end{beispiel}
Die Link-Matrix kann aus der Adjazenzmatrix des gerichteten Graphen
bestimmt werden.
Dazu ist zu beachten, dass jede Spalte durch die Anzahl der Einsen 
in dieser Spalte zu teilen ist.
Ein Zeilenvektor, der die Zahl der Einsen enthält, entsteht durch
Multiplikation mit einem Zeilenvektor $U^t$ aus lauter Einsen.
Mit dem Hadamard-Produkt ist dann die Link-Matrix durch
\[
H
=
(U(U^tA(G))^{\odot(-1)})\odot A(G)
\]
gegeben, wobei $(U^tA(G))^{\odot(-1)}$ die Inverse bezüglich des
Hadamard-Produktes ist.
%
% Freier Wille
%
\subsection{``Freier Wille''
\label{buch:subsection:freier-wille}}
Das in
Abschnitt~\eqref{buch:subsection:wahrscheinlichkeitsinterpretation}
beschriebene Modell geht unter anderem davon aus, dass der Benutzer
ausschliesslich die Navigation entlang der Links verwendet.
Natürlich gibt es viele weitere Wege, auf denen ein Besucher auf einer
bestimmten Seite landen kann.
Er kann zum Beispiel einen Link auf eine Seite per Email zugesandt
erhalten haben.
Ein solcher Link ist nicht enthalten in einer öffentlich zugänglichen
Seite des Internets und wird daher auch von der Matrix $H$ nicht
erfasst.
Eine weitere wichtige Quelle von Links sind dynamisch erzeugte Links
wie zum Beispiel die Suchresultate einer Suchmaschine.
Hier entsteht die Möglichkeit, dass die erfolgreiche Suchmaschine,
die ihre Suchresultate unter Zuhilfenahme der Matrix $H$ sortiert,
ihr eigenes Modell, auf dem ihr Erfolg basiert, torpediert.

\subsubsection{Erweiterung der Link-Matrix}
Wir bezeichnen das Ereignis, dass der Benutzer nicht die Link-Navigation
verwendet mit $F$ für ``freier Wille'', obwohl es so etwas natürlich nicht
gibt.
Die Wahrscheinlichkeit, auf der Seite $S'_j$ zu landen, setzt sich jetzt
aus den zwei Fällen $F$ und $\smash{\overline{F}}$ zusammen, für die erneut der
Satz von der totalen Wahrscheinlichkeit den Zusammenhang
\[
P(S'_j)
=
P(S'_j\mid \overline{F}) P(\overline{F})
+
P(S'_j\mid F) P(F)
\]
liefert.
Die Wahrscheinlichkeit $\alpha = P(F)$, mit der der Benutzer den
``freien Willen'' bemüht, kann experimentell durch Studien ermittelt
werden, die das Benutzerverhalten beobachten.

Die Wahrscheinlichkeit $P(S'_j\mid \overline{F})$ entsteht dadurch, dass
der Benutzer der Linknavigation folgt, sie entspricht also der früher
berechneten Wahrscheinlichkeit
\[
P(S'_j\mid \overline{F}) = \sum_{i=1}^N P(S'_j\mid S_i) P(S_i).
\]
oder in Vektorform
\[
(P(S'_j\mid \overline{F}))_{j=1,\dots,n}
=
Hp.
\]

Über die spontane Besuchswahrscheinlichkeit $P(S'_j\mid F)$ wissen wir 
nichts.
Eine erste Annahme könnte sein, dass jede Seite gleich wahrscheinlich
ist, dass also $P(S'_j\mid F)=1/N$.
Alternativ könnte man auch eine Wahrscheinlichkeitsverteilung
$q_j = P(S'_j\mid F)$ experimentell zu ermitteln versuchen.
Unter der Annahme, dass alle Seitenbesuche im Falle $F$ auf Grund
eines Sucheresultats einer Suchmaschine erfolgen, könnte die
Suchmaschine den Vektor $q$ aus ihrer eigenen Suchstatistik ermitteln.

Das erweiterte Modell kann also durch
\begin{equation}
P(S'_j)
=
\sum_{i=1}^N
\alpha P(S'_j\mid S_i) P(S_i)
+
(1-\alpha) q_j
\qquad\Rightarrow\qquad
p'
=
\alpha Hp
+
(1-\alpha)q
\label{buch:google:eqn:composed}
\end{equation}
beschrieben werden.

\subsubsection{Die Google-Matrix}
Die Formel~\eqref{buch:google:eqn:composed} erlaubt, die Wahrscheinlichkeit
$p'$ aus $p$ und $q$ zu berechnen.
Für die Ermittlung der der stationären Verteilung war jedoch die Form
$p=Hp$ besonders nützlich, weil sie das Problem in ein Eigenwertproblem
mit einem bekanntem Eigenwert verwandelt.
Wir streben daher an, die Formel~\eqref{buch:google:eqn:composed}
ebenfalls in die Form $p=Gp$ mit einer neuen Matrix $G$ zu bringen.

Die Matrixform von
\eqref{buch:google:eqn:composed}
zeigt, dass sich die gesuchte Matrix $G$ zusammensetzt aus dem Summanden
$\alpha H$ und einem weiteren Summanden $A$ mit der Eigenschaft, dass
$Ap = q$ für jeden beliebigen Wahrscheinlichkeitsvektor $p$.
Da sich die Wahrscheinlichkeiten im Vektor $p$ zu $1$ summieren, gilt
\[
\underbrace{
\begin{pmatrix}
1&1&\dots&1
\end{pmatrix}
}_{\displaystyle = U^t}
\begin{pmatrix}
P(S_1)\\
P(S_2)\\
\vdots\\
P(S_N)
\end{pmatrix}
=
P(S_1)+P(S_2)+\dots+P(S_N)=1.
\]
Man erhält also die Wirkung der gewünschte Matrix $A$, indem man $p$
erst mit dem Zeilenvektor $U^t$ und das Resultat mit $q$ multipliziert.
Es gilt daher
\[
Ap = qU^tp
\qquad\Rightarrow\qquad
A=qU^t.
\]
Ausmultipliziert ist dies die Matrix
\[
A=\begin{pmatrix}
q_1&q_1&\dots&q_1\\
q_2&q_2&\dots&q_2\\
\vdots&\vdots&\ddots&\vdots\\
q_N&q_N&\dots&q_N
\end{pmatrix}.
\]
Im Fall $q=\frac1NU$ kann dies zu
\[
A
=
\frac1N UU^t
=
\frac1N
\begin{pmatrix}
1&1&\dots&1\\
1&1&\dots&1\\
\vdots&\vdots&\ddots&\vdots\\
1&1&\dots&1
\end{pmatrix}
\]
vereinfacht werden.

\begin{definition}[Google-Matrix]
Die Matrix
\begin{equation}
G
=
\alpha H
+
\frac{1-\alpha}{N}
UU^t
\qquad\text{oder}\qquad
G
=
\alpha H
+
(1-\alpha)qU^t
\label{buch:wahrscheinlichkeit:eqn:google-matrix}
\end{equation}
heisst die
{\em Google-Matrix}.
\index{Google-Matrix}%
\end{definition}

Die Google-Matrix wurde von Sergey Brin und Larry Page 
\index{Brin, Sergey}%
\index{Page, Larry}%
in dem Artikel \cite{BRIN1998107} als Grundlage der Suchmaschine
Google beschrieben.
Sie war die Basis für den Erfolg von Google und wird dem Prinzip nach
auch heute noch zur Rangierung der Suchresultate verwendet.
Dazu muss natürlich die Gleichung $p=Gp$ gelöst werden, was
weiter unten in Abschnitt~\ref{buch:subsection:wahrscheinlichkeitsverteilung}
diskutiert wird.

Natürlich ist die heutzutage verwendete Matrix mit Sicherheit komplizierter.
In der vorgestellten Form unterstützt sie zum Beispiel auch das folgende
Geschäftsmodell, welches in der Anfangszeit von Google eine Zeit lang 
erfolgreich war.
Ein Anbieter betreibt zu diesem Zweck eine grosse Zahl von Websites,
deren Seiten im Wesentlichen aus Suchbegriffen und Links untereinander
und auf die Website des Kunden verweisen.
Dadurch entsteht für die Google-Matrix der ``Eindruck'', dass sehr viele
Websites gibt, die die Kundenwebsite als relevant für die Suchbegriffe 
ansehen.
Die Kundenwebsite wird daher in den Suchresultaten weiter oben gezeigt.
Das Problem rührt natürlich daher, dass alle Links als gleichermassen
aussagekräftig betrachtet werden.
Solche Websites werden heutzutage von der Berechnung der Google-Matrix
ausgeschlossen.

Die aktuell verwendete Variante der Google-Matrix ist natürlich ein
Betriebsgeheimnis der Firma Google.

%
% Bestimmung der zu erwartenden stationären Verteilung
%
\subsection{Wahrscheinlichkeitsverteilung
\label{buch:subsection:wahrscheinlichkeitsverteilung}}
Die Google-Matrix $G$ selbst interessiert weniger als die
Wahrscheinlichkeitsverteilung $p$.
Ziel dieses Abschnittes ist, den Vektor $p$ zu berechnen.

\subsubsection{Stationäre Verteilung}
Die Einträge $P(S_i)$ des Vektors $p$ geben die Wahrscheinlichkeit an, mit
der sich ein Benutzer auf der Seite $i$ befindet.
Wir interpretieren diese Wahrscheinlichkeit auch als ein Mass für die
Relevanz einer Seite.

Wir nehmen an, dass sich diese Wahscheinlichkeit nur langsam ändert.
Diese Annahme trifft nicht zu für neue Nachrichten, die durchaus eine
hohe Relevanz haben, für die es aber noch nicht viele Links geben kann,
die die Relevanz in der Google-Matrix erkennbar machen.
Die Annahme bedeutet, dass sich die Verteilung $p$ sehr viel langsamer 
ändert als der Navigationsprozess entlang der Links erfolgt.
In erster Näherung ist es daher zulässig, nach einem Vektor $p$ zu
suchen, der sich unter Navigation nicht ändert, also nach einer
{\em stationären} Lösung.
\index{stationäre Verteilung}%

Für eine stationäre Wahrscheinlichkeitsverteilung gilt $p'=p$.
Der Vektor $p$ erfüllt daher die Gleichung
\begin{equation}
Gp = p.
\label{buch:google:ewgleichung}
\end{equation}
$p$ ist also ein Eigenvektor der Matrix $G$ zum Eigenwert $1$.

Für ein sehr kleines Netzwerk wie im oben dargestellten Beispiel ist es
einfach, mit gängigen numerischen Algorithmen alle Eigenwerte und
Eigenvektoren zu finden.
Benötigt wird allerdings nur der Eigenvektor zum Eigenwert $1$.

\begin{beispiel}
Octave
\index{Octave}
findet den folgenden Eigenvektor zum Eigenwert $1$ der Matrix $G$,
die aus der Matrix $H$
von \eqref{buch:google:eqn:linkmatrixbeispiel}
und dem Vektor $q=\frac18U$ und $\alpha=0.9$ gebildet wurde:
\[
p_0=\begin{pmatrix}
   0.20100\\
   0.25440\\
   0.12163\\
   0.26014\\
   0.16394\\
   0.45543\\
   0.37739\\
   0.66007
\end{pmatrix}
\qquad\Rightarrow\qquad
p
=
\frac{1}{\|p_0\|_1}p_0
=
\begin{pmatrix}
   0.080595\\
   0.102004\\
   0.048769\\
   0.104305\\
   0.065735\\
   0.182609\\
   0.151320\\
   0.264664
\end{pmatrix}.
\]
Der Vektor $p_0$ ist ein Einheitsvektor in der euklidischen Norm.
Er kann daher nicht eine Wahrscheinlichkeitsverteilung sein,
da sich die Elemente nicht zu $1$ summieren.
Die $l^1$-Norm $\|\;\cdot\;\|_1$ eines Vektors ist die Summe der Beträge aller
Elemente eines Vektors.
Indem man $p_0$ durch die Summe aller Einträge von $p_0$ teilt,
erhält man die Wahrscheinlichkeitsverteilung $p$.
\end{beispiel}


\subsubsection{Potenzverfahren}
Die üblichen Algorithmen wie der von den meisten Softwarepaketen
verwendete Francis-Algorith\-mus \cite{francis:watkins_paper,buch:watkins}
\index{Francis-Algorithmus}%
zur Bestimmung von Eigenwerten
und Eigenvektoren ist für grosse Matrizen nicht praktikabel.
Da aber $1$ der betragsgrösste Eigenwert ist, kann sehr oft ein zugehöriger
Eigenvektor mit der nachfolgend beschriebenen {\em Potenzmethode}
\index{Potenzmethode}%
gefunden werden.

Sei $A$ eine $n\times n$-Matrix, der Einfachheit halber nehmen wir an,
dass die Eigenwerte $\lambda_1>\lambda_2\ge \dots\ge \lambda_n$
absteigend geordnet sind,
und dass $v_1,\dots,v_n$ zugehörige linear unabhängige Eigenvektoren sind.
Ein beliebiger Vektor $v$ lässt sich in der Eigenbasis von $A$
als
\[
v = a_1v_1+\dots+a_nv_n
\]
ausdrücken.
Wendet man darauf die Matrix $A$ $k$-mal an, erhält man
\[
A^kv
=
a_1\lambda_1^k v_1 
+
a_2\lambda_2^k v_2
+
\dots
+
a_n\lambda_n^k v_n.
\]
Da $\lambda_1$ der betragsmässig grösste Eigenwert ist, wird der Vektor
$A^kv$ ungefähr mit der $k$-ten Potenz von $\lambda_1$ anwachsen.
Indem man durch $\lambda_1^k$ teilt, erhält man
\[
\frac{1}{\lambda_1^k} A^k v
=
a_1v_1
+
a_2\biggl(\frac{\lambda_2}{\lambda_1}\biggr)^k v_2
+
\dots
+
a_n\biggl(\frac{\lambda_n}{\lambda_1}\biggr)^k v_n.
\]
Da alle Brüche Betrag $<1$ haben, konvergiert die rechte Seite für $k\to\infty$
gegeben den  ersten Summanden.
Durch wiederholte Anwendung von $A/\lambda_1$ auf einen (fast) beliebigen
Startvektor $v$ erhält man also eine Folge von Vektoren, die gegen einen
Eigenvektor zum Eigenwert $\lambda_1$ konvergiert.

Numerische Ungenauigkeiten können bewirken, dass die Iteration mit der
Matrix $A/\lambda_1$ trotzdem nicht konvergiert.
Man kann dies komponsieren, indem man nach jeder Iteration normiert.
Da der gesuchte Eigenvektor eine Wahrscheinlichkeitsverteilung sein muss,
muss die $l^1$-Norm $1$ sein.
Statt mit der euklidischen $l^2$-Norm zu normieren, normiert man daher
besser mit der $l^1$-Norm.
Damit ergibt sich das folgende Verfahren zur Bestimmung der Pagerank-Verteilung
$p$ für die Google-Matrix.

\begin{satz}
Für die Google-Matrix $p$ konvergiert die Folge 
\[
p^{(0)} = u,
\qquad
p^{(k+1)} = \frac{G^{(k)}}{\| G^{(k)} \|_1}
\]
gegen die stationäre Verteilung $p$ mit $Gp=p$.
\end{satz}