LaTeX-examples/documents/DYCOS/Sprungtypen.tex

\subsection{Sprungtypen}\label{sec:sprungtypen}
Die beiden bereits definierten Sprungtypen, der strukturelle Sprung
sowie der inhaltliche Mehrfachsprung 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 Mehrfachsprü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 man dies machen, 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 man einen inhaltlichen
Mehrfachsprung machen will 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 Mehrfachsprungs.
\end{enumerate}

Konkret könnte also ein inhaltlicher Mehrfachsprung 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 Mehrfachsprung}
  \label{alg:DYCOS-content-multihop}
    \begin{algorithmic}[1]
        \Procedure{InhaltlicherMehrfachsprung}{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}