diff options
Diffstat (limited to 'buch/chapters/80-wahrscheinlichkeit/google.tex')
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/google.tex | 86 |
1 files changed, 24 insertions, 62 deletions
diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex index bb5597d..ca78b3d 100644 --- a/buch/chapters/80-wahrscheinlichkeit/google.tex +++ b/buch/chapters/80-wahrscheinlichkeit/google.tex @@ -6,57 +6,6 @@ \section{Google-Matrix \label{buch:section:google-matrix}} \rhead{Google-Matrix} - -% -% Ein Modell für Webseitenbesucher -% -\subsection{Ein Modell für Webseitenbesucher -\label{buch:subsection:modell-fuer-webseitenbesucher}} -\begin{figure} -\centering -\begin{tikzpicture}[>=latex,thick] -\foreach \x in {0,3,6,9}{ - \foreach \y in {0,3}{ - \fill[color=white] ({\x},{\y}) circle[radius=0.3]; - \draw ({\x},{\y}) circle[radius=0.3]; - } -} -\node at (0,3) {$1$}; -\node at (0,0) {$2$}; -\node at (3,3) {$3$}; -\node at (3,0) {$4$}; -\node at (6,3) {$5$}; -\node at (6,0) {$6$}; -\node at (9,3) {$7$}; -\node at (9,0) {$8$}; -% 1 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (3,3); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (0,0); -% 2 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,0) to[out=-20,in=-160] (3,0); -% 3 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (6,3); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (0,0); -% 4 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,3); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,0); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) to[out=160,in=20] (0,0); -% 5 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,3); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,0); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (6,0); -% 6 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,0) to[out=20,in=160] (9,0); -% 7 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) .. controls (7.5,4) .. (6,4) -- (3,4) .. controls (1.5,4) .. (0,3); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) to[out=-110,in=110] (9,0); -% 8 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=-160,in=-20] (6,0); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=70,in=-70] (9,3); -\end{tikzpicture} -\caption{Modell-Internet als Beispiel für die Link-Matrix und die Google-Matrix. -\label{buch:figure:modellinternet}} -\end{figure} Das Internet besteht aus einer grossen Zahl von Websites, etwa 400~Millionen aktiven Websites, jede besteht aus vielen einzelnen Seiten. Es ist daher angemessen von $N\approx 10^9$ verschiedenen Seiten auszugehen. @@ -84,6 +33,18 @@ bedeutet aber auch, dass nach Synonymen oder alternative Formen eines Wortes separat gesucht werden muss, was die Übersichtlichkeit wieder zerstört. +% +% 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} + Das kombinierte Vorkommen von Wörtern oder Begriffen alleine kann also nicht ausreichen, um die Seiten zum Beispiel einem Fachgebiet zuzuordnen. Dazu muss eine externe Informationsquelle angezapft werden. @@ -358,7 +319,7 @@ Da sich die Wahrscheinlichkeiten im Vektor $p$ zu $1$ summieren, gilt \begin{pmatrix} 1&1&\dots&1 \end{pmatrix} -}_{\displaystyle = u^t} +}_{\displaystyle = U^t} \begin{pmatrix} P(S_1)\\ P(S_2)\\ @@ -369,12 +330,12 @@ P(S_N) 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. +erst mit dem Zeilenvektor $U^t$ und das Resultat mit $q$ multipliziert. Es gilt daher \[ -Ap = qu^tp +Ap = qU^tp \qquad\Rightarrow\qquad -A=qu^t. +A=qU^t. \] Ausmultipliziert ist dies die Matrix \[ @@ -385,11 +346,11 @@ q_2&q_2&\dots&q_2\\ q_N&q_N&\dots&q_N \end{pmatrix}. \] -Im Fall $q=\frac1Nu$ kann dies zu +Im Fall $q=\frac1NU$ kann dies zu \[ A = -\frac1N uu^t +\frac1N UU^t = \frac1N \begin{pmatrix} @@ -401,22 +362,23 @@ A \] vereinfacht werden. -\begin{definition} +\begin{definition}[Google-Matrix] Die Matrix -\[ +\begin{equation} G = \alpha H + \frac{1-\alpha}{N} -uu^t +UU^t \qquad\text{oder}\qquad G = \alpha H + -(1-\alpha)qu^t -\] +(1-\alpha)qU^t +\label{buch:wahrscheinlichkeit:eqn:google-matrix} +\end{equation} heisst die {\em Google-Matrix}. \index{Google-Matrix}% |