mirror of
https://github.com/MartinThoma/LaTeX-examples.git
synced 2025-04-19 11:38:05 +02:00
47 lines
2.7 KiB
TeX
47 lines
2.7 KiB
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.
|