LaTeX-examples/documents/Proseminar-Netzwerkanalyse/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.

    %Sei außerdem $f: V \rightarrow \mathcal{P}(V)$ eine Abbildung
    %mit der Eigenschaft:
    %\[ \forall v \in V \forall v' \in f(v): \exists \text{Weg von } v \text{ nach } v'\]

    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 \textit{//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}