LaTeX-examples/documents/DYCOS/Einleitung.tex

\subsection{Motivation}
Teilweise gelabelte Netzwerke sind allgegenwärtig. Publikationsdatenbanken
mit Publikationen als Knoten, Literaturverweisen und Zitaten als Kanten
sowie Tags oder Kategorien als Labels;
Wikipedia mit Artikeln als Knoten, Links als Kanten und Kategorien
als Labels sowie soziale Netzwerke mit Eigenschaften der Benutzer
als Labels sind drei Beispiele dafür.
Häufig sind Labels nur teilweise vorhanden und es ist wünschenswert die 
fehlenden Labels zu ergänzen. 

\subsection{Problemstellung}
Gegeben ist ein Graph, der teilweise gelabelt ist. Zusätzlich stehen
zu einer Teilmenge der Knoten Texte bereit. Gesucht sind nun Labels
für alle Knoten, die bisher noch nicht gelabelt 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$ die Kantenmenge und $V_{L,t} \subseteq V_t$ die Menge der 
    gelabelten Knoten jeweils zum Zeitpunkt $t$ bezeichne.
    Außerdem sei $L_t$ die Menge aller zum Zeitpunkt $t$ vergebenen
    Labels und $f:V_{L,t} \rightarrow L_t$ die Funktion, die einen
    Knoten auf sein Label abbildet.

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

    Gesucht sind nun Labels für $V_t \setminus V_{L,t}$, also
    $\tilde{f}: V_t \rightarrow L_t$ mit 
    $\tilde{f}|_{V_{L,t}} = f$.
\end{definition}

\subsection{Herausforderungen}
Die Graphen, für die dieser Algorithmus konzipiert wurde,
sind viele $\num{10000}$~Knoten groß und dynamisch. Das bedeutet, es 
kommen neue Knoten und eventuell auch neue Kanten hinzu bzw. Kanten 
oder Knoten werden entfernt. Außerdem stehen textuelle Inhalte zu den 
Knoten bereit, die bei der Klassifikation genutzt werden können.
Bei kleinen Modifikationen sollte nicht alles nochmals berechnen 
werden müssen, sondern basierend auf zuvor
berechneten Labels sollte die Klassifizierung modifiziert werden.