aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/verkehr
diff options
context:
space:
mode:
authorNunigan <37363304+Nunigan@users.noreply.github.com>2021-08-05 18:05:44 +0200
committerGitHub <noreply@github.com>2021-08-05 18:05:44 +0200
commitad357d3fcef71296d209d8bb9f2d88ee9602136c (patch)
treef9301740a761c485398f4fc7d63cf377ccc5a888 /buch/papers/verkehr
parentupdate paper (diff)
parentMerge pull request #71 from paschost/patch-4 (diff)
downloadSeminarMatrizen-ad357d3fcef71296d209d8bb9f2d88ee9602136c.tar.gz
SeminarMatrizen-ad357d3fcef71296d209d8bb9f2d88ee9602136c.zip
Merge branch 'AndreasFMueller:master' into 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.