| 123456789101112131415161718192021222324252627282930313233343536373839404142 |
- \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. Zustäzlich 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 \powerset(L_t)$ die Funktion, die einen
- Knoten auf seine Labels 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.
- Das bedeutet, es ist wünschenswert bei kleinen Modifikationen nicht
- nochmals alles neu berechnen zu müssen, sondern basierend auf zuvor
- berechneten Labels die Klassifizierung modifizieren zu können.
|
