aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/verkehr
diff options
context:
space:
mode:
authorNao Pross <np@0hm.ch>2021-08-06 13:39:44 +0200
committerNao Pross <np@0hm.ch>2021-08-06 13:39:44 +0200
commita2f881beae521260443ea185d25646ebb94e9f87 (patch)
tree5f94929a4a29e216f094a4e62a2979eed0812882 /buch/papers/verkehr
parentCorrections from feedback (diff)
parentadd images for clifford (diff)
downloadSeminarMatrizen-a2f881beae521260443ea185d25646ebb94e9f87.tar.gz
SeminarMatrizen-a2f881beae521260443ea185d25646ebb94e9f87.zip
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to 'buch/papers/verkehr')
-rw-r--r--buch/papers/verkehr/section1.tex18
1 files changed, 9 insertions, 9 deletions
diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex
index 6ac86ad..8994066 100644
--- a/buch/papers/verkehr/section1.tex
+++ b/buch/papers/verkehr/section1.tex
@@ -54,13 +54,13 @@ Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er
\subsection{Anwendung Floyd-Warshall-Algorithmus}
%THEORIE...
-In einem ersten Schritt wird eine Gewichtsmatrix $W$ mit den Matrixeinträgen $W[i, j]$ erstellt.
+In einem ersten Schritt wird eine Gewichtsmatrix $W$ mit den Matrixeinträgen $W(i, j)$ erstellt.
Der Algorithmus berechnet danach in einer Hauptschleife alle Knoten $k$ von 1 bis $n$.
Dabei versucht er in jeder Iteration alle Wege von $i$ nach $j$ durch die Wege $(i, k)$ und $(k, j)$ zu verbessern.
Falls dieser mögliche Umweg zu einer Verbesserung führt, wird der entsprechende Eintrag aktualisiert.
Die aktuelle Gewichtung der Pfade wird mit
-\begin{equation}d[i, j]=\min[d[i,j], d[i,k] + d[k,i]]\end{equation}
+\begin{equation}d(i, j)=\min\{d(i,j), d(i,k) + d(k,i)\}\end{equation}
ermittelt.
@@ -68,14 +68,14 @@ ermittelt.
\section{PageRank-Algorithmus}
Der PageRank-Algorithmus wurde von den Gründern von Google, Larry Page und Sergey Brin im Jahr 1996 entwickelt und zum Patent angemeldet. Zwei Jahre später gründeten sie ihr Unternehmen Google Inc.
Beim PageRank-Algorithmus handelt es sich nicht um einen Suchalgorithmus, stattdessen werden Knoten aufgrund der Vernetzung des vorliegenden Graphen bewertet.
-Verwendet wird er beispielsweise um die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur zu bewerten und relevante Suchergebnisse zu ermittteln. Der PageRank wird umso höher, je mehr hochwertige Links auf eine Webseite verweisen und je höher die Gewichtung einer Webseite ist, desto grösser ist der Effekt.\\
+Verwendet wird er beispielsweise um die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur zu bewerten und relevante Suchergebnisse zu ermittteln. Der PageRank wird umso höher, je mehr hochwertige Links auf eine Webseite verweisen und je höher die Gewichtung einer Webseite ist, desto grösser ist der Effekt.
Dabei handelt es sich um einen iterativen Prozess. Ausgegangen wird von der Adjazenz-Matrix $A$, für welche folgendes gilt:
\begin{equation}
-A_{i,j}=\left\{ \begin{matrix}
-1 & \text{Kante von $j$ nach $i$} \\ 0 & \text{keine Kante von $j$ nach $i$}
-\end{matrix}
- \right.
+A_{i,j} = \begin{cases}
+1&\quad\text{Kante von $j$ nach $i$}\\
+0&\quad\text{keine Kante von $j$ nach $i$}
+\end{cases}
\label{verkehr:Adja}
\end{equation}
@@ -86,8 +86,8 @@ Grundsätzlich setzt sich der PageRank Algorithmus mit der Fragestellung auseina
Für ungerichtete Graphen mit $n$ Knoten gilt \begin{equation}A_{i,j}=A_{j,i}\end{equation} und weiter \begin{equation}A_{i,i}=0\quad\forall i\in \left\{1\dots n\right\}\end{equation}
Beim PageRank-Algorithmus wird eine abgewandelte Form der Adjazenz-Matrix verwendet.
-Dabei werden die Matrix-Einträge spaltenweise durch die jeweilige Spaltensumme geteilt:
-\( P_{i,j}=\frac{A_{i,j}}{\sum_{i=1}^{n}A_{i,j}} \)
+Dabei werden die Matrix-Einträge spaltenweise durch die jeweilige Spaltensumme geteilt, so entsteht die Link-Matrix
+\[ P_{i,j}=\frac{A_{i,j}}{\sum_{k=1}^{n}A_{k,j}} \]
Anschliessend multipliziert man diese Matrix $P$ mit einem Spaltenvektor $\Vec{r_0}$ mit $n$ Einträgen, für welchen gilt:
\( \Vec{r_0}(i) = \frac{1}{n} \quad\forall i\in \left\{1\dots n\right\} \)
Dieser Vektor stellt ein neutrales Ranking dar. Alle Knoten werden gleich gewichtet.