\begin{slide}{Page Rank (I)}

\glqq Definition\grqq: 
eine Webseite (URL) ist wichtig,
wenn wichtige Seiten auf sie zeigen.

\begin{itemize}
\item 
Eingabe: 
Matrix \verb|link :: (URL, URL) -> Double|
mit \verb|link(u,v)=| Wahrscheinlichkeit,
daß der Besucher von $u$ zu $v$ geht.
\item
Gesucht: Vektor \verb|w :: URL -> Double|
mit  \verb|w * link = w|
\end{itemize}

Modifikationen für
\begin{itemize}
\item eindeutige Lösbarkeit
\item effiziente Lösbarkeit
\end{itemize}

\end{slide}

\begin{slide}{Page Rank (Eindeutigkeit)}

  \begin{itemize}
  \item aus der Link-Matrix: Sackgassen entfernen
    (dort zufällig fortsetzen)
  \item diese Matrix mit völlig zufälliger
    Verteilung überlagern
  \end{itemize}

Resultat ist (quadr.) stochastische 
Matrix mit positiven Einträgen,
nach Satz von Perron/Frobenius
\begin{itemize}
\item 
besitzt diese einen eindeutigen größten reellen
Eigenwert
\item und zugehöriger Eigenvektor
hat positive Einträge.
\end{itemize}


\end{slide}

\begin{slide}{Page Rank (Berechnung)}

durch wiederholte Multiplikation:

beginne mit $w_0=$ Gleichverteilung,

dann $w_{i+1} = L \cdot w_i$
genügend oft 

(bis $|w_{i+1}-w_i|<\epsilon$)

\bigskip

diese Vektor/Matrix-Multiplikation
kann ebenfalls mit Map/Reduce ausgeführt werden.

(Welches sind die Schlüssel?)

(Beachte: Matrix ist dünn besetzt. Warum?)

\bigskip

Quelle: Massimo Franceschet:
\emph{PageRank: Standing on the Shoulders of Giants} Comm. ACM 6/2011,
\url{http://cacm.acm.org/magazines/2011/6/108660}

\end{slide}
