Einleitung.tex

Im Folgenden werden in \cref{sec:Motivation} einige Beispiele, in denen
der DYCOS-Algorithmus Anwendung finden könnte, dargelegt. In
\cref{sec:Problemstellung} wird die Problemstellung formal definiert
und in \cref{sec:Herausforderungen} wird auf besondere Herausforderungen der
Aufgabenstellung hingewiesen.

\subsection{Motivation}\label{sec:Motivation}
Teilweise beschriftete Graphen sind allgegenwärtig. Publikationsdatenbanken mit
Publikationen als Knoten, Literaturverweisen und Zitaten als Kanten sowie von
Nutzern vergebene Beschriftungen (sog. {\it Tags}) oder Kategorien als
Knotenbeschriftungen; Wikipedia mit Artikeln als Knoten, Links als Kanten und
Kategorien als Knotenbeschriftungen sowie soziale Netzwerke mit Eigenschaften
der Benutzer als Knotenbeschriftungen sind drei Beispiele dafür. Häufig sind
Knotenbeschriftungen nur teilweise vorhanden und es ist wünschenswert die
fehlenden Knotenbeschriftungen automatisiert zu ergänzen.

\subsection{Problemstellung}\label{sec:Problemstellung}
Gegeben ist ein Graph, dessen Knoten teilweise beschriftet sind. Zusätzlich
stehen zu einer Teilmenge der Knoten Texte bereit. Gesucht sind nun
Knotenbeschriftungen für alle Knoten, die bisher noch nicht beschriftet sind.\\

\begin{definition}[Knotenklassifierungsproblem]\label{def:Knotenklassifizierungsproblem}
    Sei $G_t = (V_t, E_t, V_{L,t})$ ein gerichteter Graph, wobei $V_t$ die
    Menge aller Knoten, $E_t \subseteq V_t \times V_t$ die Kantenmenge und
    $V_{L,t} \subseteq V_t$ die Menge der beschrifteten Knoten jeweils zum
    Zeitpunkt $t$ bezeichne. Außerdem sei $L_t$ die Menge aller zum Zeitpunkt
    $t$ vergebenen Knotenbeschriftungen und $f:V_{L,t} \rightarrow L_t$ die
    Funktion, die einen Knoten auf seine Beschriftung abbildet.

    Weiter sei für jeden Knoten $v \in V$ eine (eventuell leere) Textmenge
    $T(v)$ gegeben.

    Gesucht sind nun Beschriftungen für $V_t \setminus V_{L,t}$, also
    $\tilde{f}: V_t \setminus V_{L,t} \rightarrow L_t$. Die Aufgabe, zu $G_t$
    die Funktion $\tilde{f}$ zu finden heißt
    \textit{Knotenklassifierungsproblem}.
\end{definition}

\subsection{Herausforderungen}\label{sec:Herausforderungen}
Die Graphen, für die dieser Algorithmus konzipiert wurde, sind viele
$\num{10000}$~Knoten groß und dynamisch. \enquote{Dynamisch} bedeutet in diesem
Kontext, dass neue Knoten und eventuell auch neue Kanten hinzu kommen bzw.
Kanten oder Knoten werden entfernt werden. Außerdem stehen textuelle Inhalte zu
den Knoten bereit, die bei der Klassifikation genutzt werden können. Bei
kleinen Änderungen sollte nicht alles nochmals berechnen werden müssen, sondern
basierend auf zuvor berechneten Knotenbeschriftungen sollte die Klassifizierung
angepasst werden.