LaTeX-examples/publications/Proseminar-Netzwerkanalyse/SchwaechenVerbesserungen.tex

Bei der Anwendung des in \cite{aggarwal2011} vorgestellten Algorithmus auf
reale Datensätze könnten zwei Probleme auftreten, die im Folgenden erläutert
werden. Außerdem werden Verbesserungen vorgeschlagen, die es allerdings noch zu
untersuchen gilt.

\subsection{Anzahl der Knotenbeschriftungen}
So, wie der DYCOS-Algorithmus vorgestellt wurde, können nur Graphen bearbeitet
werden, deren Knoten jeweils höchstens eine Beschriftung haben. In vielen
Fällen, wie z.~B. Wikipedia mit Kategorien als Knotenbeschriftungen haben
Knoten jedoch viele Beschriftungen.

Auf einen ersten Blick ist diese Schwäche einfach zu beheben, indem man beim
zählen der Knotenbeschriftungen für jeden Knoten jedes Beschriftung zählt. Dann
wäre noch die Frage zu klären, mit wie vielen Beschriftungen der betrachtete
Knoten beschriftet werden soll.

Jedoch ist z.~B. bei Wikipedia-Artikeln auf den Knoten eine Hierarchie
definiert. So ist die Kategorie \enquote{Klassifikationsverfahren} eine
Unterkategorie von \enquote{Klassifikation}. Bei dem Kategorisieren von
Artikeln sind möglichst spezifische Kategorien vorzuziehen, also kann man nicht
einfach bei dem Auftreten der Kategorie \enquote{Klassifikationsverfahren}
sowohl für diese Kategorie als auch für die Kategorie \enquote{Klassifikation}
zählen.


\subsection{Überanpassung und Reklassifizierung}
Aggarwal und Li beschreiben in \cite{aggarwal2011} nicht, auf welche Knoten der
Klassifizierungsalgorithmus angewendet werden soll. Jedoch ist die Reihenfolge
der Klassifizierung relevant. Dazu folgendes Minimalbeispiel:

Gegeben sei ein dynamischer Graph ohne textuelle Inhalte. Zum Zeitpunkt $t=1$
habe dieser Graph genau einen Knoten $v_1$ und $v_1$  sei mit dem $A$
beschriftet. Zum Zeitpunkt $t=2$ komme ein nicht beschrifteter Knoten $v_2$
sowie die Kante $(v_2, v_1)$ hinzu.\\
Nun wird der DYCOS-Algorithmus auf diesen Knoten angewendet und $v_2$ mit $A$
beschriftet.\\
Zum Zeitpunkt $t=3$ komme ein Knoten $v_3$, der mit $B$ beschriftet ist, und
die Kante $(v_2, v_3)$ hinzu. \Cref{fig:Formen} visualisiert diesen Vorgang.

\begin{figure}[ht]
    \centering
    \subfloat[$t=1$]{
        \input{figures/graph-t1.tex}
        \label{fig:graph-t1}
    }%
    \subfloat[$t=2$]{
        \input{figures/graph-t2.tex}
        \label{fig:graph-t2}
    }

    \subfloat[$t=3$]{
        \input{figures/graph-t3.tex}
        \label{fig:graph-t3}
    }%
    \subfloat[$t=4$]{
        \input{figures/graph-t4.tex}
        \label{fig:graph-t4}
    }%
    \caption{Minimalbeispiel für den Einfluss früherer DYCOS-Anwendungen}
    \label{fig:Formen}
\end{figure}

Würde man nun den DYCOS-Algorithmus erst jetzt, also anstelle von Zeitpunkt
$t=2$ zum Zeitpunkt $t=3$ auf den Knoten $v_2$ anwenden, so würde eine
\SI{50}{\percent}-Wahrscheinlichkeit bestehen, dass dieser mit $B$ beschriftet
wird. Aber in diesem Beispiel wurde der Knoten schon zum Zeitpunkt $t=2$
beschriftet. Obwohl es in diesem kleinem Beispiel noch keine Rolle spielt, wird
das Problem klar, wenn man weitere Knoten einfügt:

Wird zum Zeitpunkt $t=4$ ein unbeschrifteter Knoten $v_4$ und die Kanten
$(v_1, v_4)$, $(v_2, v_4)$, $(v_3, v_4)$ hinzugefügt, so ist die
Wahrscheinlichkeit, dass $v_4$ mit $A$ beschriftet wird bei $\frac{2}{3}$.
Werden die unbeschrifteten Knoten jedoch erst jetzt und alle gemeinsam
beschriftet, so ist die Wahrscheinlichkeit für $A$ als Beschriftung bei nur $50\%$.
Bei dem DYCOS-Algorithmus findet also eine Überanpassung an vergangene
Beschriftungen statt.

Das Reklassifizieren von Knoten könnte eine mögliche Lösung für dieses
Problem sein. Knoten, die durch den DYCOS-Algorithmus beschriftet wurden
könnten eine Lebenszeit bekommen (TTL, Time to Live). Ist diese
abgelaufen, wird der DYCOS-Algorithmus erneut auf den Knoten angewendet.