\medskip\noindent
Lawrence Page und Sergey Brin beschreiben in ''The PageRank citation ranking: Bringing order to the Web''  \cite{Brin/Page/98a} das von Google verwendete PageRank Verfahren zur Analyse der Webtopologie. Dieses Verfahren basiert auf der Idee eines globales Rankings von Webseiten, das durch Analyse der Verbindungsstruktur des Netzes erzeugt wird. Die Autoren nehmen an, das wichtige Seiten besonders oft von anderen Seiten verlinkt werden, ein Webautor signalisiert durch einen Link auf eine andere Seite die Bereitschaft eine andere Quelle in den eigenen Inhalten zu zitieren.

\medskip\noindent
Das Web ist ein mittels HTTP Protokoll realisiertes, virtuelles Netz aus HTML-Dokumenten, die durch Hyperlinks miteinander verbunden sind. Das Verfahren Nutzt diese Struktur in dem es das Web als Graph betrachtet.

\begin{description}
\item[Webgraph] - Es sei $G = ( V,E)$ ein gerichteter Graph mit:
\begin{itemize}
\item $V$ der Knotenmenge statischer Webseiten
\item $E$ der Kantenmenge aus Hyperlinks
\end{itemize}
\end{description}
Jeder Knoten des Webgraphen ist also ein HTML-Dokument, verbunden mit anderen Dokumenten durch Anchor Tags. Eingehende Kanten eines Dokuments bezeichnen wir als $B$ Backlinks oder ''inedges'', ausgehende Kanten als $F$ Forward Links oder ''outedges''.

\begin{figure}[h]
	\centerline{ \includegraphics [height=50mm] {bilder_marius/prstrukt} }
	\caption{A und B sind Backlinks - C erreichbar durch Forward Links}
\end{figure}

\medskip\noindent
Der PageRank Algorithmus betrachtet die Backlinks einer Webseite, allerdings werden nicht alle eingehenden Links gleich bewertet. Der Rank einer Seite ist die Summe der Ranks ihrer Backlinks.

\begin{description}
\item[PageRank] Sei $u$ eine Webseite und ein Knoten in $G$
\begin{itemize}
 \item $F_{u}$ die Menge aller Forward Links von $u$, 
 \item $B_{u}$ die Menge aller Backlinks von $u$, 
 \item $N_{u}=\vert F_{u} \vert$ die Anzahl aller Nachfolger von $u$
 \item $d$ soll Damping Faktor zur Normierung des Ranks sein
 \item $E$ sei eine Initialbelegung des statischen PageRanks über alle Seiten.
 \end{itemize}
 $R$ ist eine Rankingfunktion von $u$ und ihrer Vorg"angerin $v$, der Form:
 \begin{center}
 $R(u) = d \displaystyle \sum  _{v \in B_{u}} \frac{R(v)}{N_{v}} + dE(u)$
 \end{center}
  \end{description} 

\medskip\noindent  
Der PageRank einer Seite $u$ wird also rekursiv aus der Summe der PageRanks derjenigen Seiten die auf $u$ verweisen. Allerdings wird nur eine einzige Verbindung zu $u$, anteilig zur der Menge aller Links betrachtet. Für die Analyse des  Algorithmus betrachten wir Adjazenzmatrix $A$ des Webgraphen $G$ mit:
  \begin{itemize} 
  \item $a_{v,u} = \frac{1}{N_{v}}$ falls eine Kante von $v$ nach $u$ existiert.
  \item $a_{v,u} = 0$ sonst.
  \end{itemize}
  
  
\begin{description}
\item[PageRank] Starte in $R_{0} = E$ der Initialbelegung und laufe durch die folgende Schleife bis $R_{j}$ konvergiert.  
\begin{itemize}
 \item $R_{i+1} \leftarrow AR_{i}$\\ 
 \item $d \leftarrow \vert \vert R_{i} \vert \vert _{1} - \vert \vert R_{i+1} \vert \vert _{1}$
 \item $R_{i+1} \leftarrow R_{i+1} + dE$
 \end{itemize}
 \end{description}   
 
 \begin{figure}[h]
	\centerline{ \includegraphics [height=50mm] {bilder_marius/priteration} }
	\caption{Eine Iteration der vereinfachten Rankingfunktion}
\end{figure}

\medskip\noindent
Ohne die Initialbelegung und den Damping Faktor würde der
PageRank bei jeder Iteration zu den Senken fliessen. Also zu Seiten die auf keine anderen Seiten verlinken (Dangling Links) oder auf dem Webgraph Kreise bilden (Rank Sinks). Um den negativen Effekt der Dangling Links entgegenzuwirken, werden die PageRanks dieser Seiten erst berechnet, wenn die eigentliche Berechnung bereits abgeschlossen ist.
 \medskip\noindent
Seiten die durch gemeinsame Verlinkung auf dem Webgraph Kreise bilden und nur auf sich selbst verweisen, erzeugen eine Schleife in der der Rank steigt aber nicht weiter verteilt wird, da dieser Kreis keine ausgehenden Kanten besitzt. 

\begin{figure}[h]
	\centerline{ \includegraphics [height=30mm] {bilder_marius/prdangling} }
	\caption{Ein Kreis im Webgraph: Rank Sink}
\end{figure}
\medskip\noindent
Der Damping Faktor, der stets zwischen 0 und 1 liegt wirkt diesem Problem entgegen und verringert den Ausmaß der PageRank Weitergabe. 

\medskip\noindent
Das statische PageRank Verfahren von Google ist Unabhängig von den Inhalten einer Webseite. Der Algorithmus konvergiert schnell und liefert selbst nach wenigen Iterationen gute Ergebnisse. Nach 45 Iterationen ist die PageRank Berechnung von 161 Mio. Links abgeschlossen. Bei Verdoppelung der Anzahl von Links konvergiert konvergiert der Algorithmus bereits nach 52,5 Iterationen. Der Algortihmus wird der Datenaufbereitung ausgeführt und ist schont Ressourcen die zu Query Zeit benötigt werden.

\medskip\noindent
Zusätzlich lässt sich das Verfahren, wie in ''A Unified Probabilistic Framework for Web Page Scoring Systems'' von Diligenti, Gori etal. \cite{Diligenti/etal/2004a} beschrieben, auch probabilistisch als Rando Surfer Modell  interpretieren.


 

