LaTeX-examples/documents/DYCOS/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. Er klassifiziert Knoten, indem mehrfach Random Walks startend
bei dem zu klassifizierenden Knoten gemacht werden und die Labels
der besuchten Knoten gezählt werden. Das Label, das am häufigsten
vorgekommen ist, wird als Label 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 nimmt jedoch nicht einfach den Graphen für 
dieses Verfahren, sondern erweitert ihn mit Hilfe der zur Verfügung
stehenden Texte.

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 Abschnitt~\ref{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.

\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 Mehrfachsprünge:

\begin{definition}
    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 \textbf{struktureller Sprung}.
\end{definition}

Im Gegensatz dazu benutzten inhaltliche Mehrfachsprünge
tatsächlich die Grapherweiterung:

\begin{definition}
    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 Nachbar von $v' \in V_t$ von $w$
    ein \textbf{inhaltlicher Mehrfachsprung}. $v'$ ist also genau
    einen Sprung über einen Wortknoten $w$ von $v$ entfernt.
\end{definition}

Der DYCOS-Algorithmus betrachtet die Texte, die einem Knoten 
zugeornet 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.

\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 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 \enquote{Wort} die Anzahl der Vorkommen von 
          \enquote{Wort} 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.
    \item An einigen Stellen macht ein assoziatives Array, auch 
          \enquote{dictionary} oder \enquote{map} genannt, sinn.
          Zustätzlich ist es nützlich, wenn diese Datenstruktur für 
          unbekannte Schlüssel keinen Fehler ausgibt, sondern für diese
          Schlüssel den Wert 0 annimmt. Eine solche Datenstruktur
          wird in Python \texttt{defaultdict} genannt und ich werde
          im Folgenden diese Benennung beibehalten.
\end{itemize}

\input{Sprungtypen}
\input{Vokabularbestimmung}

\subsection{Der Algorithmus}
Der DYCOS-Algorithmus verwendet nun für jeden Knoten der gelabelt wird
$r$ Random Walks der Länge $l$, wobei mit einer Wahrscheinlichkeit 
$p_S$ ein struktureller $l$-Sprung und mit einer Wahrscheinlichkeit
von $(1-p_S)$ ein inhaltlicher $l$-Mehrfachsprung gemacht wird.

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

Im Folgenden werde ich den DYCOS-Algorithmus als Pseudocode vorstellen.
Dafür benötigt man die beiden Hilfsfunktionen für den strukturellen
Sprung sowie den inhaltlichen Mehrfachsprung:

\begin{algorithm}[H]
    \begin{algorithmic}[1]
        \Require \\$\G_t = (\N_t, \A_t, \T_t)$ (Netzwerk),\\
                 $r$ (Anzahl der Random Walks),\\
                 $l$ (Länge eines Random Walks),\\
                 $p_s$ (Wahrscheinlichkeit eines strukturellen Sprungs),\\
                 $q$ (Anzahl der betrachteten Knoten nach der Aggregatanalyse)
        \Ensure  Klassifikation von $\N_t \setminus \T_t$\\
        \\

        \ForAll{Knoten $v$ in $\N_t \setminus \T_t$}
            \State $d \gets $ defaultdict
            \For{$i$ von $1$ bis $r$}
                \State $w \gets v$
                \For{$j$ von $1$ bis $l$}
                    \State $sprungTyp \gets \Call{random}{0, 1}$
                    \If{$sprungTyp \leq p_S$}
                        \State $w \gets$ \Call{SturkturellerSprung}{$w$}
                    \Else
                        \State $w \gets$ \Call{InhaltlicherMehrfachsprung}{$w$}
                    \EndIf
                    \State $w \gets v.\Call{GetLabel}{ }$ \Comment{Zähle das Label}
                    \State $d[w] \gets d[w] + 1$
                \EndFor
            \EndFor

            \If{$d$ ist leer} \Comment{Es wurde kein gelabelter 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 Label $M_H$ zufällig eines aus}
            \State $label \gets \Call{Random}{M_H}$ 
            \State $v.\Call{AddLabel}{label}$ \Comment{und weise dieses $v$ zu}
        \EndFor
        \State \Return Labels für $\N_t \setminus \T_t$
    \end{algorithmic}
\caption{DYCOS-Algorithmus}
\label{alg:DYCOS}
\end{algorithm}