| 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 |
- \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
- sind drei Beispiele dafür.
- Da Labels nur teilweise vorhanden sind, ist es wünschenswert die
- fehlenden Labels zu ergänzen.
- \subsection{Problemstellung}
- Das Knotenklassifierungsproblem sei wie folgt definiert:\\
- \begin{definition}[Knotenklassifierungsproblem]\label{def:Knotenklassifizierungsproblem}
- Sei $\G_t = (\N_t, \A_t, \T_t)$ ein Netzwerk,
- wobei $\N_t$ die Menge aller Knoten,
- $\A_t$ die Kantenmenge und $\T_t \subseteq \N_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:\T_t \rightarrow \L_t$ die Funktion, die einen
- Knoten auf sein Label abbildet.
- Gesucht sind nun Labels für $\N_t \setminus \T_t$, also
- $\tilde{f}:\N_t \rightarrow \L_t$ mit
- $\tilde{f}|_{\T_t} = f$.
- \end{definition}
- Wir haben häufig zusätzlich zu dem Graphen $\G_t$ und der Label-Funktion
- $f$ aus Definition~\ref{def:Knotenklassifizierungsproblem} noch
- textuelle Inhalte, die Knoten zugeornet werden.
- \subsection{Herausforderungen}
- Die beispielhaft aufgeführen Netzwerke 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.
- Der DYCOS-Algorithmus nutzt diese und kann auf große, dynamische
- Netzwerken angewandt werden.
- Der DYCOS-Algorithmus nutzt Random Walks im Graphen, startend
- von dem zu klassifizierenden Knoten $n$. Dabei wird pro Random Walk
- gezählt, welche Klasse $K$ am häufigsten gesehen wird. Der Knoten $n$
- wird dann als zu $K$ zugehörig klassifiziert.
|
