LaTeX-examples/documents/Proseminar-Netzwerkanalyse/Sprungtypen.tex

\subsection{Sprungtypen}\label{sec:sprungtypen}
Die beiden bereits definierten Sprungtypen, der strukturelle Sprung sowie der
inhaltliche Zweifachsprung werden im Folgenden erklärt.
\goodbreak
Der strukturelle Sprung entspricht einer zufälligen Wahl eines Nachbarknotens,
wie es in \cref{alg:DYCOS-structural-hop} gezeigt wird.
\begin{algorithm}[H]
    \begin{algorithmic}[1]
        \Procedure{SturkturellerSprung}{Knoten $v$, Anzahl $q$}
            \State $n \gets v.\Call{NeighborCount}{}$ \Comment{Wähle aus der Liste der Nachbarknoten}
            \State $r \gets \Call{RandomInt}{0, n-1}$ \Comment{einen zufällig aus}
            \State $v \gets v.\Call{Next}{r}$ \Comment{Gehe zu diesem Knoten}
            \State \Return $v$
        \EndProcedure
    \end{algorithmic}
\caption{Struktureller Sprung}
\label{alg:DYCOS-structural-hop}
\end{algorithm}

Bei inhaltlichen Zweifachsprüngen ist jedoch nicht sinnvoll so strikt nach der
Definition vorzugehen,  also direkt von einem strukturellem Knoten $v \in V_t$
zu einem mit $v$ verbundenen Wortknoten $w \in W_t$ zu springen und von diesem
wieder zu einem verbundenem strukturellem Knoten $v' \in V_t$. Würde dies
gemacht werden, wäre zu befürchten, dass aufgrund von Homonymen die Qualität der
Klassifizierung verringert wird. So hat \enquote{Brücke} im Deutschen viele
Bedeutungen. Gemeint sein können z.~B. das Bauwerk, das Entwurfsmuster der
objektorientierten Programmierung oder ein Teil des Gehirns.

Deshalb wird für jeden Knoten $v$, von dem aus ein inhaltlicher
Zweifachsprung gemacht werden soll folgende Textanalyse durchgeführt:
\begin{enumerate}[label=C\arabic*,ref=C\arabic*]
    \item \label{step:c1} Gehe alle in $v$ startenden Random Walks der Länge $2$ durch
          und erstelle eine Liste $L$ der erreichbaren Knoten $v'$. Speichere
          außerdem, durch wie viele Pfade diese Knoten $v'$ jeweils erreichbar
          sind.
    \item \label{step:c2} Betrachte im Folgenden nur die Top-$q$ Knoten bzgl.
          der Anzahl der Pfade von $v$ nach $v'$, wobei $q \in \mathbb{N}$
          eine zu wählende Konstante des DYCOS-Algorithmus ist.\footnote{Sowohl für den DBLP, als auch für den
CORA-Datensatz wurde in \cite[S. 364]{aggarwal2011} $q=10$ gewählt.}
          Diese Knotenmenge heiße im Folgenden $T(v)$ und $p(v, v')$ sei die
          Anzahl der Pfade von $v$ über einen Wortknoten nach $v'$.
    \item \label{step:c3} Wähle mit Wahrscheinlichkeit
          $\frac{p(v, v')}{\sum_{w \in T(v)} p(v, w)}$ den Knoten $v' \in T(v)$
          als Ziel des Zweifachsprungs.
\end{enumerate}

Konkret könnte also ein inhaltlicher Zweifachsprung sowie wie in
\cref{alg:DYCOS-content-multihop} beschrieben umgesetzt werden.
Der Algorithmus bekommt einen Startknoten $v \in V_T$ und
einen $q \in \mathbb{N}$ als Parameter. $q$ ist ein Parameter der
für den DYCOS-Algorithmus zu wählen ist. Dieser Parameter beschränkt
die Anzahl der möglichen Zielknoten $v' \in V_T$ auf diejenigen
$q$ Knoten, die $v$ bzgl. der Textanalyse am ähnlichsten sind.

In \cref{alg:l2} bis \cref{alg:l5} wird \cref{step:c1} durchgeführt und alle
erreichbaren Knoten in $reachableNodes$ mit der Anzahl der Pfade, durch die sie
erreicht werden können, gespeichert.

In \cref{alg:l6} wird \cref{step:c2} durchgeführt. Ab hier gilt
\[ |T| = \begin{cases}q               &\text{falls } |reachableNodes|\geq q\\
                     |reachableNodes| &\text{sonst }\end{cases}\]

Bei der Wahl der Datenstruktur von $T$ ist zu beachten, dass man in
\cref{alg:21} über Indizes auf Elemente aus $T$ zugreifen können muss.

In \cref{alg:l8} bis \ref{alg:l13} wird ein assoziatives Array erstellt, das
von $v' \in T(v)$ auf die relative Häufigkeit bzgl. aller Pfade von $v$ zu
Knoten aus den Top-$q$ abbildet.

In allen folgenden Zeilen wird \cref{step:c3} durchgeführt. In \cref{alg:15}
bis \cref{alg:22} wird ein Knoten $v' \in T(v)$ mit einer Wahrscheinlichkeit,
die seiner relativen Häufigkeit am Anteil der Pfaden der Länge 2 von $v$ nach
$v'$ über einen beliebigen Wortknoten entspricht ausgewählt und schließlich
zurückgegeben.

\begin{algorithm}
  \caption{Inhaltlicher Zweifachsprung}
  \label{alg:DYCOS-content-multihop}
    \begin{algorithmic}[1]
        \Procedure{InhaltlicherZweifachsprung}{Knoten $v \in V_T$, $q \in \mathbb{N}$}
            \State $erreichbareKnoten \gets$ leeres assoziatives Array\label{alg:l2}
            \ForAll{Wortknoten $w$ in $v.\Call{getWordNodes}{ }$}
                \ForAll{Strukturknoten $x$ in $w.\Call{getStructuralNodes}{ }$}
                    \If{$!erreichbareKnoten.\Call{hasKey}{x}$}
                        \State $erreichbareKnoten[x] \gets 0$
                    \EndIf
                    \State $erreichbareKnoten[x] \gets erreichbareKnoten[x] + 1$
                \EndFor
            \EndFor\label{alg:l5}
            \State \label{alg:l6} $T \gets \Call{max}{erreichbareKnoten, q}$
            \\
            \State \label{alg:l8} $s \gets 0$
            \ForAll{Knoten $x \in T$}
                \State $s \gets s + erreichbareKnoten[x]$
            \EndFor
            \State $relativeHaeufigkeit \gets $ leeres assoziatives Array
            \ForAll{Knoten $x \in T$}
                \State $relativeHaeufigkeit \gets \frac{erreichbareKnoten[x]}{s}$
            \EndFor\label{alg:l13}
            \\
            \State \label{alg:15} $random \gets \Call{random}{0, 1}$
            \State $r \gets 0.0$
            \State $i \gets 0$
            \While{$s < random$}
                \State $r \gets r + relativeHaeufigkeit[i]$
                \State $i \gets i + 1$
            \EndWhile

            \State $v \gets T[i-1]$ \label{alg:21}
            \State \Return $v$ \label{alg:22}
        \EndProcedure
    \end{algorithmic}
\end{algorithm}