DYCOS-Algorithmus.tex

\subsection{Überblick}
DYCOS (\underline{DY}namic \underline{C}lassification algorithm with
c\underline{O}ntent and \underline{S}tructure) ist ein
Knotenklassifizierungsalgorithmus, der Ursprünglich in \cite{aggarwal2011}
vorgestellt wurde.

Ein zentrales Element des DYCOS-Algorithmus ist der sog. {\it Random Walk}:

\begin{definition}[Random Walk, Sprung]
    Sei $G = (V, E)$ mit $E \subseteq V \times V$ ein Graph und
    $v_0 \in V$ ein Knoten des Graphen.

    Ein Random Walk der Länge $l$ auf $G$, startend bei $v_0$ ist nun der
    zeitdiskrete stochastische Prozess, der $v_i$ auf einen zufällig gewählten
    Nachbarn $v_{i+1}$ abbildet (für $i \in 0, \dots, l-1$). Die Abbildung $v_i
    \mapsto v_{i+1}$ heißt ein Sprung.
\end{definition}

Der DYCOS-Algorithmus klassifiziert einzelne Knoten, indem $r$ Random Walks der
Länge $l$, startend bei dem zu klassifizierenden Knoten $v$ gemacht werden.
Dabei werden die Beschriftungen der besuchten Knoten gezählt. Die Beschriftung,
die am häufigsten vorgekommen ist, wird als Beschriftung für $v$ gewählt. DYCOS
nutzt also die sog. Homophilie, d.~h. die Eigenschaft, dass Knoten, die nur
wenige Hops von einander entfernt sind, häufig auch ähnlich sind \cite{bhagat}.
Der DYCOS-Algorithmus arbeitet jedoch nicht direkt auf dem Graphen, sondern
erweitert ihn mit Hilfe der zur Verfügung stehenden Texte. Wie diese
Erweiterung erstellt wird, wird im Folgenden erklärt.\\
Für diese Erweiterung wird zuerst wird Vokabular $W_t$ bestimmt, das
charakteristisch für eine Knotengruppe ist. Wie das gemacht werden kann und
warum nicht einfach jedes Wort in das Vokabular aufgenommen wird, wird in
\cref{sec:vokabularbestimmung} erläutert.\\
Nach der Bestimmung des Vokabulars wird für jedes Wort im Vokabular ein
Wortknoten zum Graphen hinzugefügt. Alle Knoten, die der Graph zuvor hatte,
werden nun \enquote{Strukturknoten} genannt.
Ein Strukturknoten $v$ wird genau dann mit einem Wortknoten $w \in W_t$
verbunden, wenn $w$ in einem Text von $v$ vorkommt. \Cref{fig:erweiterter-graph}
zeigt beispielhaft den so entstehenden, semi-bipartiten Graphen.
Der DYCOS-Algorithmus betrachtet also die Texte, die einem Knoten
zugeordnet sind, als eine Multimenge von Wörtern. Das heißt, zum einen
wird nicht auf die Reihenfolge der Wörter geachtet, zum anderen wird
bei Texten eines Knotens nicht zwischen verschiedenen
Texten unterschieden. Jedoch wird die Anzahl der Vorkommen
jedes Wortes berücksichtigt.

\begin{figure}[htp]
    \centering
    \input{figures/graph-content-and-structure.tex}
    \caption{Erweiterter Graph}
    \label{fig:erweiterter-graph}
\end{figure}

Entsprechend werden zwei unterschiedliche Sprungtypen unterschieden, die
strukturellen Sprünge und inhaltliche Zweifachsprünge:

\begin{definition}[struktureller Sprung]
    Sei $G_{E,t} = (V_t, E_{S,t} \cup E_{W,t}, V_{L,t}, W_{t})$ der
    um die Wortknoten $W_{t}$ erweiterte Graph.

    Dann heißt das zufällige wechseln des aktuell betrachteten
    Knoten $v \in V_t$ zu einem benachbartem Knoten $w \in V_t$
    ein \textit{struktureller Sprung}.
\end{definition}
\goodbreak
Im Gegensatz dazu benutzten inhaltliche Zweifachsprünge tatsächlich die
Grapherweiterung:
\begin{definition}[inhaltlicher Zweifachsprung]
    Sei $G_t = (V_t, E_{S,t} \cup E_{W,t}, V_{L,t}, W_{t})$ der um die
    Wortknoten $W_{t}$ erweiterte Graph.

    Dann heißt das zufällige wechseln des aktuell betrachteten Knoten $v \in
    V_t$ zu einem benachbartem Knoten $w \in W_t$ und weiter zu einem
    zufälligem Nachbar $v' \in V_t$ von $w$ ein inhaltlicher Zweifachsprung.
\end{definition}

Jeder inhaltliche Zweifachsprung beginnt und endet also in einem
Strukturknoten, springt über einen Wortknoten und ist ein Pfad der Länge~2.

Ob in einem Sprung der Random Walks ein struktureller Sprung oder ein
inhaltlicher Zweifachsprung gemacht wird, wird jedes mal zufällig neu
entschieden. Dafür wird der Parameter $0 \leq p_S \leq 1$ für den Algorithmus
gewählt. Mit einer Wahrscheinlichkeit von $p_S$ wird ein struktureller Sprung
durchgeführt und mit einer Wahrscheinlichkeit von $(1-p_S)$ ein modifizierter
inhaltlicher Zweifachsprung, wie er in \cref{sec:sprungtypen} erklärt wird,
gemacht. Der Parameter $p_S$ gibt an, wie wichtig die Struktur des Graphen im
Verhältnis zu den textuellen Inhalten ist. Bei $p_S = 0$ werden ausschließlich
die Texte betrachtet, bei $p_S = 1$ ausschließlich die Struktur des Graphen.

Die Vokabularbestimmung kann zu jedem Zeitpunkt $t$ durchgeführt werden, muss
es aber nicht.

In \cref{alg:DYCOS} steht der DYCOS-Algorithmus in Form von Pseudocode:
In \cref{alg1:l8} wird für jeden unbeschrifteten Knoten
durch die folgenden Zeilen eine Beschriftung gewählt.

\Cref{alg1:l10} führt $r$ Random Walks durch. In \cref{alg1:l11} wird eine
temporäre Variable für den aktuell betrachteten Knoten angelegt.

In \cref{alg1:l12} bis \cref{alg1:l21} werden einzelne Random Walks der Länge
$l$ durchgeführt, wobei die beobachteten Beschriftungen gezählt werden und mit
einer Wahrscheinlichkeit von $p_S$ ein struktureller Sprung durchgeführt wird.

\begin{algorithm}[ht]
    \begin{algorithmic}[1]
        \Require \\$G_{E,t} = (V_t, E_{S,t} \cup E_{W,t}, V_{L,t}, W_t)$ (Erweiterter Graph),\\
                 $r$ (Anzahl der Random Walks),\\
                 $l$ (Länge eines Random Walks),\\
                 $p_s$ (Wahrscheinlichkeit eines strukturellen Sprungs),\\
                 $q$ (Anzahl der betrachteten Knoten in der Clusteranalyse)
        \Ensure  Klassifikation von $V_t \setminus V_{L,t}$\\
        \\

        \ForAll{Knoten $v \in V_t \setminus V_{L,t}$}\label{alg1:l8}
            \State $d \gets $ leeres assoziatives Array
            \For{$i = 1, \dots,r$}\label{alg1:l10}
                \State $w \gets v$\label{alg1:l11}
                \For{$j= 1, \dots, l$}\label{alg1:l12}
                    \State $sprungTyp \gets \Call{random}{0, 1}$
                    \If{$sprungTyp \leq p_S$}
                        \State $w \gets$ \Call{SturkturellerSprung}{$w$}
                    \Else
                        \State $w \gets$ \Call{InhaltlicherZweifachsprung}{$w$}
                    \EndIf
                    \State $beschriftung \gets w.\Call{GetLabel}{ }$
                    \If{$!d.\Call{hasKey}{beschriftung}$}
                        \State $d[beschriftung] \gets 0$
                    \EndIf
                    \State $d[beschriftung] \gets d[beschriftung] + 1$
                \EndFor\label{alg1:l21}
            \EndFor

            \If{$d$.\Call{isEmpty}{ }} \Comment{Es wurde kein beschrifteter Knoten gesehen}
                \State $M_H \gets \Call{HäufigsteLabelImGraph}{ }$
            \Else
                \State $M_H \gets \Call{max}{d}$
            \EndIf
            \\
            \State \Comment{Wähle aus der Menge der häufigsten Beschriftungen $M_H$ zufällig eine aus}
            \State $label \gets \Call{Random}{M_H}$
            \State $v.\Call{AddLabel}{label}$ \Comment{und weise dieses $v$ zu}
        \EndFor
        \State \Return Beschriftungen für $V_t \setminus V_{L,t}$
    \end{algorithmic}
\caption{DYCOS-Algorithmus}
\label{alg:DYCOS}
\end{algorithm}

\subsection{Datenstrukturen}
Zusätzlich zu dem gerichteten Graphen $G_t = (V_t, E_t, V_{L,t})$ verwaltet der
DYCOS-Algorithmus zwei weitere Datenstrukturen:
\begin{itemize}
    \item Für jeden Knoten $v \in V_t$ werden die vorkommenden Wörter,
          die auch im Vokabular $W_t$ sind,
          und deren Anzahl gespeichert. Das könnte z.~B. über ein
          assoziatives Array (auch \enquote{dictionary} oder
            \enquote{map} genannt) geschehen. Wörter, die nicht in
          Texten von $v$ vorkommen, sind nicht im Array. Für
          alle vorkommenden Wörter ist der gespeicherte Wert zum
          Schlüssel $w \in W_t$ die Anzahl der Vorkommen von
          $w$ in den Texten von $v$.
    \item Für jedes Wort des Vokabulars $W_t$ wird eine Liste von
          Knoten verwaltet, in deren Texten das Wort vorkommt.
          Diese Liste wird bei den inhaltlichen Zweifachsprung,
          der in \cref{sec:sprungtypen} erklärt wird,
          verwendet.
\end{itemize}

\input{Sprungtypen}
\input{Vokabularbestimmung}