communities.tex

Bereits sehr früh in der Vorlesung stellten wir fest, dass beobachtete Netze in der Regel dünn sind.
Auf ein Netzwerk mit menschlichen Teilnehmern bezogen könnte man dies so interpretieren, dass nicht jede Person mit jeder anderen sprechen kann (würde man mit jedem Menschen weltweit genau eine Sekunde lang sprechen, wäre man damit mehr als 250 Jahre beschäftigt).
Menschen neigen aber dazu, sich in Gruppen bzw. Gemeinschaften (engl. communities) zu organisieren;
Beispiele sind die Familie, Freunde, Arbeitskollegen, Sportclubs, Lern- und Forschungsgruppen.
Wir finden aber Communities auch in anderen Netzwerken (\zB im WWW oder biochemischen Netzwerken).

Hierbei handelt es sich in der Regel um verhältnismäßig kleine Gruppen, die jedoch eng interagieren.
Wir sehen aber bereits an den Beispielen, dass ein Mensch zu mehreren Gruppen gehören kann.
Man spricht dann von überlappenden Communities.
Überlappende Communities können auch hierarchisch angelegt sein: Eine Firma mag in verschiedene Standorte mit je verschiedenen Sparten mit je verschiedenen Teams organisiert sein.
Der Einfachheit halber konzentrieren wir uns aber auf den nichtüberlappenden Fall, in dem jeder Teilnehmer einer Gruppe zugeordnet wird.

Leider gibt es selbst für diesen einfachen Fall keine scharfe und allgemeingültige Definition, was eine Community darstellt.
Um sie dennoch mit Werkzeugen der Network Science greifen zu können, treffen wir zwei Annahmen (nach \cite{barabasi2014network}):

\begin{enumerate}[label=H\arabic*), ref=H\arabic*]
    \item\label{enum:contains_structure}
          \emph{Der betrachtete Graph enthält die Struktur des beobachteten Netzwerks.}
          Auch wenn dieser Punkt offensichtlich erscheint, müssen wir immer berücksichtigen, dass der betrachtete Graph eines beobachteten Netzwerks eine verlustbehaftete Modellierung darstellt.
          So ist es nicht unwahrscheinlich, dass wir in einem Freundschafts- oder Kommunikationsnetz Freundeskreise identifizieren können.
          Hingegen werden wir in einem Stammbaum im Allgemeinen keine Arbeitsgruppen finden.

    \item\label{enum:high_internal_degree}
          Eingangs argumentierten wir, dass eine Community einen starken internen Zusammenhalt hat.
          In Verbindung mit der vorherigen Annahme ergibt sich dann:
          \emph{Eine Community hat --~im Vergleich zum Gesamtgraphen~-- einen relativ hohen internen Grad.}
\end{enumerate}

Beginnen wir mit einem Extrem von Annahme \ref{enum:high_internal_degree}:
Eine Clique hat immer den maximalen internen Grad, daher liegt es nahe, jede maximale (\dh nicht erweiterbare) Clique als eine Community aufzufassen.
Im Kleinen funktioniert das gut: In sozialen Netzen etwa gibt es viele Dreiecke.
Wenn Person $A$ zwei Freunde $B$ und $C$ hat, dann ist es nicht unwahrscheinlich, dass auch $B$ und $C$ in Kontakt stehen.
Das entstehende Dreieck ist eine 3-Clique.

Größere Gruppen müssen aber im Allgemeinen nicht vollständig verbunden sein;
man stelle sich etwa eine Schulklasse im Kommunikationsnetz einer Schule vor.
Nicht jeder Schüler wird ständig mit jedem anderem sprechen.
Im Schnitt sollten aber --~schon aufgrund der räumlichen Nähe über längere Zeiträume~-- innerhalb der Klasse mehr Verbindungen vorhanden sein als zu anderen Klassen oder gar Stufen.

\def\intdeg{\deg^{\text{int}}_C}
\def\extdeg{\deg^{\text{ext}}_C}

Wir fassen daher den Begriff weiter und unterscheiden zwischen starken und schwachen Communities (nach \cite{barabasi2014network}).
Sei $C \subseteq V$ eine Community, die wir als Knotenteilmenge modellieren.
Dann sei $\intdeg(v)$ die Anzahl der Nachbarn von $v$ in $C$ und $\extdeg(v)$ die Anzahl der Nachbarn außerhalb von $C$.
Es gilt also
\begin{equation}
    \intdeg(v) + \extdeg(v) = \deg(v) \qquad \forall v \in V
\end{equation}

\begin{itemize}
    \item Wir nennen $C$ eine \emph{starke Community}, falls jeder Knoten in $C$ strikt mehr interne als externe Nachbarn hat, \dh
          \begin{equation}
              \intdeg(v) > \extdeg(v) \qquad \forall v \in C.
          \end{equation}

    \item Wir nennen $C$ eine \emph{schwache Community}, falls der gesamte interne Grad die Anzahl der externen Nachbarn übersteigt, \dh
          \begin{equation}
              \sum_{v\in C}\intdeg(v) > \sum_{v\in C} \extdeg(v).
          \end{equation}
\end{itemize}

\section{Erkennen von Communities}
Das Erkennen von Communities ist eine wichtige Aufgabe in Network Science, die zwei verwandte Algorithmenklassen umfasst:
Community-Detection-Algorithmen und Graph-Partitioning-Algorithmen.
Beide Typen haben gemein, dass sie einen Graphen in möglichst zusammengehörige Untergruppen teilen sollen.

Der Unterschied ist in der Anwendung und Eingabe.
Ein Partitionierungsalgorithmus wird \zB verwendet, wenn ein großer Graph auf mehrere Prozessoren verteilt werden soll.
Wir wissen, dass wir $P$ Teile brauchen, und die Aufgabe ist es \zB, die Anzahl der Kanten zwischen den Partitionsklassen zu minieren;
ggf. werden weitere Einschränkungen gesetzt, \zB dass die Teile ungefähr gleich groß sind (\zB minimal balanced edge cuts).
Oft handelt es sich also um Unterroutinen, um eine Berechnung zu \qq{vereinfachen}, und ist damit besonders im Algorithmen-Design zu finden.

Community-Detection-Algorithmen hingegen müssen selbst \qq{herausfinden}, wie viele Communities vorhanden sind~--
die resultierende Zerlegung ist also vor allem durch die Eingabe bestimmt.
Im Kontext von Network Science sind also Community-Detection-Algorithmen interessant.

Leider sollte es wenig überraschen, dass die meisten Probleme in Partitionierung und Community-Detection \NP-schwer sind.
Konsequenterweise steigt auch die Anzahl der möglichen Partition schon bei Bipartitionen in $\Omega(2^{\card{V}})$.

Wir müssen daher in der Regel Approximationsalgorithmen nutzen, um Communities zu finden.
Um einen iterativen Optimierungsalgorithmus zu konstruieren, benötigen wir ein Qualitätsmaß für eine Graphpartitionierung.
Hierbei ist die sog. Modularity eine gängige Wahl.

\section{Modularity}
Sei $A = (a_{ij})_{ij}$ die Adjazenzmatrix eines ungerichteten Graphen $G = (V, E)$.
Sei $C = (c_1, \ldots, c_n) \in [n_c]^n$ eine Auflistung der Communities $1, \ldots, n_c$, zu denen die Knoten jeweils gehören.
Dann ist eine übliche Definition der Modularity~$Q$ des Graphen
\begin{equation}
    Q = \frac{1}{2m} \smashoperator{\sum_{i,j \in V}} \left( a_{ij} - \frac{\deg(i)\deg(j)}{2m} \right) \delta(c_i, c_j),
\end{equation}
mit Kronecker-Delta $\delta(x,y) = 1$, falls $x=y$, und $\delta(x,y) = 0$, falls $x \ne y$.
Die Modularity kann einen Wertebereich von $[-1/2, 1]$ einnehmen.
Wir nehmen an, dass eine gute Partitionierung des Graphen einen hohen Modularity-Wert annimmt.

\begin{exercise}
    Drücke $Q$ unter Verwendung von $\intdeg(v)$ und $\extdeg(v)$ aus.
\end{exercise}

Versuchen wir zunächst, die Aussage von~$Q$ intuitiv zu verstehen.
Der erste Term, \dh $\sum_{i,j} a_{ij} \delta(c_i, c_j)$, zählt die Kanten innerhalb und kann nur über das Kronecker-Delta beeinflusst werden.
Er wird maximal, falls alle Knoten in einer Community sind~-- das ist nicht sonderlich nützlich.

Der Beitrag des zweiten Terms, \dh $-\sum_{i,j} \deg(i)\deg(j) \delta(c_i, c_j)/2m$, ist nichtpositiv.
Wir maximieren ihn, indem wir ihn möglichst nahe an $0$ bringen.
Das geschieht, indem wir viele Communities erzeugen, die alle einen möglichst geringen internen Gesamtgrad haben.
Das Optimieren der Modularity ist also immer ein Kompromiss dieser beiden Größen.

\subsection{Ein Greedy-Algorithmus}
Das Finden von Community-Strukturen mit optimaler Modularity ist --~natürlich~-- \NP-schwer (und trivialerweise in \NP).~\cite{DBLP:journals/tkde/BrandesDGGHNW08}
Daher müssen wir für praktische Netzwerke eine Approximation nutzen, \zB folgenden Greedy-Algorithmus:

\begin{enumerate}
    \item Weise jedem Knoten seine eigene Community zu.
    \item Suche unter allen Paaren von mit mindestens einer Kante verbundenen Communities ein Paar, dessen Verschmelzung $Q$ am meisten erhöht.
    \item Verschmilz die beiden Communities und wiederhole die Schritte 2 und 3, bis nur noch eine Community verbleibt.
    \item Gebe unter allen erzeugten Zwischenergebnisse das Clustering mit maximaler Modularity aus.
\end{enumerate}

Diese Art der Modularity-Maximierung leidet unter dem sog. \emph{resolution limit} (siehe \cite{barabasi2014network} für Details).
Stark vereinfacht besagt es, dass für zwei verbundene Knoten $i$ und~$j$ mit $\deg(i) \deg(j) < 2m$ die erwartete Kantenanzahl zwischen ihnen kleiner als die tatsächliche ist.
Die Modularity steigt daher zwangsweise durch deren Vernetzung.
Eine Konsequenz hieraus ist, dass der Greedy-Algorithmus Communities mit einem internen Grad von weniger als $\sqrt{2m}$ verschmilzt, sobald sie mit einer Kante verbunden sind.

In vielen beobachteten Netzwerken gibt es jedoch deutlich kleinere Gruppen, die nicht auf diese Weise gefunden werden können.
Das Problem kann \zB mit dem Louvain-Algorithmus relativiert werden.