einleitung.tex

\qq{Network Science} und \qq{Algorithm Engineering} sind zwei aktive und interdisziplinäre Forschungsfelder.
Beide Felder sind relativ jung (etwa 20 bis 30 Jahre alt) und haben sich in den letzten Jahren stark weiterentwickelt.
Sie könnten beide unabhängig von einander ganze Studiengänge füllen (und tun es auch).
In dieser Veranstaltung möchten wir also nicht die Vereinigung beider Felder beleuchten, sondern uns einige Themen in ihrem Schnitt ansehen.
Dennoch sollten wir grob die Felder charakterisieren.

\emph{Network Science} beschäftigt sich mit der Analyse und Modellierung von komplexen Netzwerken.
Beispiele sind soziale, Kommunikations- und Verkehrsnetze, biologische Netzwerke und viele mehr.
Sie zeichnen sich durch sogenanntes \emph{emergentes Verhalten} aus: Ohne dass einzelnen Knoten oder Kanten bewusst darauf hinarbeiten, entsteht ein komplexes Verhalten des Gesamtsystems.
In sozialen Netzen bilden sich \zB lokal stark vernetzte Gruppen (Communities), es gibt einige zentrale Teilnehmer, die übermäßig stark vernetzt sind (Celebrities), und Netze haben überraschend geringe Distanzen zwischen Nutzern.
Network Science versucht, diese Eigenschaften zu finden und zu verstehen.
Hierzu vereinigt es Methoden aus Mathematik, Informatik, und Physik.

\vspace{-2em}
\floatmarginfigure{
    \scalebox{0.9}{
        \begin{tikzpicture}[
            box/.style={draw, minimum width=8em, minimum height=2.5em, inner sep=0.2em, align=center},
            arr/.style={draw, >={LaTeX[width=1em,length=1em]}, thick, ->, labelcolor}
            ]
            \node[box] (s0) at (0,  0.0em) {Algorithmen-\\[-0.4em]entwurf};
            \node[box] (s1) at (0, -4.5em) {Theoretische \\[-0.4em] Analyse};
            \node[box] (s2) at (0, -9.0em) {Implementierung};
            \node[box] (s3) at (0,-13.5em) {Experimentelle \\[-0.4em] Analyse};

            \path[arr] (s0) to (s1);
            \path[arr] (s1) to (s2);
            \path[arr] (s2) to (s3);

            \path[arr] (s3.east) to ++(1.5em,0) |- (s0);
            \path[arr] (s3.east) to ++(1.5em,0) |- (s2);
        \end{tikzpicture}}
    \caption{Algorithm Engineering Zyklus}
    \label{fig:intro/algorithm-engineering}}
Ziel des \emph{Algorithm Engineering} ist es, die Spaltung zwischen Theorie und Praxis im Algorithmenentwurf zu überbrücken.
Es geht also darum, theoretisch effiziente als auch praktisch schnelle und implementierbare Algorithmen zu entwickeln.
Hierbei kommt oft die in \cref{fig:intro/algorithm-engineering} dargestellte zyklische Entwurfsmethode zum Einsatz:

Wir entwerfen meist zuerst einen Algorithmus und versuchen, dessen Performance theoretisch vorherzusagen;
diese Hypothesen werden dann experimentell überprüft und -- je nach Ergebnis -- der Algorithmus oder die Analyse (\zB Average Case statt Worst Case) angepasst.
Dieser Zyklus wird wiederholt, bis ein Algorithmus gefunden ist, der sowohl praktisch gut funktioniert als auch theoretisch verstanden ist.

Um praktisch nützliche Vorhersagen treffen zu können, verwendet man im Algorithm Engineering möglichst realistische Modelle für die Maschine und die Eingabedaten.
Zur Analyse von Graphalgorithmen benötigen wir also geeignete Modelle für Netzwerke.
Zur Analyse von großen Netzwerken benötigen wir wiederum effiziente Algorithmen.
So ergänzen sich die beiden Felder.

\section{Über diese Veranstaltung}
Lernziele dieser Veranstaltung beinhalten:
\begin{itemize}
    \item Wichtige Eigenschaften von beobachteten Netzwerken (\zB Dichte, Gradverteilung, Zusammenhang, Durchmesser, lokales Clustering, globales Clustering)
    \item Methoden, diese Eigenschaften nachzubilden und zu erklären
    \item Zufallsgraphen und ihre Eigenschaften
    \item Effiziente Algorithmen für und auf Zufallsgraphen
    \item Effiziente, randomisierte Algorithmen (wir betrachten viele Graphgeneratoren -- die Techniken eignen sich aber viel allgemeiner für diverse Simulationsaufgaben)
\end{itemize}

\section{Begrifflichkeiten}
Ein \emph{Netzwerk} ist ein System, in dem Personen/Agenten/Objekte (etc.) miteinander in Relation stehen (\zB durch eine Freundschaft, ein Gespräch usw.).
\emph{Graphen} sind ein abstraktes Modell dieses Systems: Wir identifizieren die Akteure mit den Knoten und die Beziehungen mit den Kanten.
Wenn wir ein Netzwerk aus der echten Welt in einen Graphen übersetzen, sprechen wir oft von einem \emph{beobachteten Netzwerk}.
Diese Abbildung geht oft mit dem Verlust von Informationen einher (wir wollen für den Anwendungsfall Unwesentliches ausblenden) und ist oft nicht eindeutig.

\begin{example}
    Die akademische Arbeit ist von Kollaboration geprägt -- Wissenschaftler arbeiten zusammen und publizieren schließlich gemeinsam ihre Ergebnisse.
    Es handelt sich also ganz klar um ein Netzwerk.
    Wie modellieren wir aber den zugrunde liegenden Graphen?
    Hier ein paar Ansätze:

    \begin{itemize}
        \item
              Wir können Autoren als Knoten auffassen und eine Kante zwischen zwei Autoren ziehen, wenn sie zusammen publiziert haben.
              Hierbei geht die Information darüber verloren, wie oft zwei Wissenschaftler kollaborierten.
              Dies könnte man etwa durch Kantengewichte ergänzen, die die Anzahl der gemeinsamen Publikationen kodieren.

        \item Wir können die Autoren als Knoten und die Publikationen als Kanten auffassen.
              Da im Allgemeinen die Anzahl der Autoren pro Publikation unbeschränkt ist, ergibt sich ein Hypergraph (ein Graph mit Kanten zwischen mehr als zwei Knoten).

        \item Wir können die Autoren \emph{und} Publikationen als Knoten auffassen und je eine Publikation mit allen Urhebern verbinden.
              Dieser Graph ist bipartit\footnote{Wir können jeden Hypergraph analog in einen bipartiten Graphen übersetzen.}, da weder Autoren noch Publikationen untereinander verbunden sind.
              Kanten könnten jetzt sogar noch weitere Informationen tragen, \zB den Hauptautor.\qedhere
    \end{itemize}
\end{example}

\noindent
Keines dieser Modelle ist \emph{richtig} oder \emph{falsch} -- die Wahl hängt davon ab, was wir mit dem Graphen bezwecken.