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 (z.B. 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}
    \item[H1)]
          \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[H2)]
          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 Gesamtgraph--- einen relativ hohen internen Grad.}
\end{enumerate}

Beginnen wir mit einem extrem von Annahme H2:
Eine Clique hat immer den maximalen internen Grad, daher liegt es nahe, jede maximale (d.h. 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 Community 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, d.h.
          \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, d.h.
          \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 z.B. verwendet, wenn ein großer Graph auf mehrere Prozessoren verteilt werden soll.
Wir wissen, dass wir $P$ Teile brauchen, und die Aufgabe ist es z.B. die Anzahl der Kanten zwischen den Partitionsklassen zu minieren;
ggf. werden weitere Einschränkungen gesetzt, z.B. dass die Teile ungefähr gleich groß sind (z.B. minimal balanced edge cuts).
Oft handelt es sich also um Unterroutinen um eine Berechnung zu \qq{vereinfachen} und 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 Partitionierungs/Community Detection \NP-schwer sind.
Konsequenterweise steigt auch die Anzahl der möglichen Partition schon bei Bipartitionen in $\Omega(2^|V|)$.

Wir müssen daher in der Regel Approximationsalgorithmen nutzen, um Communities zu finden.
Um einen iterativen Optimierungsalgorithmus zu konstruieren, benötigen ein Qualitätsmaß für ein 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$ von Knoten den Communities $1, \ldots, n_c$.
Dann ist eine übliche Definition der Modularity~$Q$ des Graphens
\begin{equation}
    Q = \frac{1}{2m} \sum_{i,j \in V} \left( a_{ij} - \frac{\deg(i)\deg(v)}{2m} \right) \delta(c_i, c_j),
\end{equation}
wobei das Kroneckerdelta $\delta(x,y) = 1$ falls $x=y$ und $\delta(x,y) = 0$ für $x \ne y$.
Die Modularity kann einen Wertebereich von $[-1/2, 1]$ einnehmen.
Wir nehmen an, dass eine gute Partitionierung des Graphs einen hohen Modularitywert 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, d.h. die Summe über $\sum_{i,j} a_{ij} \delta(c_i, c_j)$ zählt die Kanten innerhalb   kann nur über das Kronckerdelta beeinflusst werden.
Er wird maximal, falls alle Knoten in einer Community sind --- das ist nicht sonderlich nützlich.

Der Beitrag des zweiten Terms $-\sum_{i,j} \deg(i)\deg(v) \delta(c_i, c_j)/2m$ ist nicht-positiv.
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 Communitystruktur mit optimaler Modularity ist ---natürlich--- \NP-schwer (und trivial in \NP).~\cite{DBLP:journals/tkde/BrandesDGGHNW08}
Daher müssen wir für praktische Netzwerke eine Approximation nutzen, z.B. folgenden Greedyalgorithmus:

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

Diese Art der Modularitymaximierung leidet unter dem sog. \emph{resolution limit} (siehe \cite{barabasi2014network} für Details).
Stark vereinfacht, ist für zwei verbundene Knoten $u$ und $v$ mit $\deg(u) \deg(v) < 2m$ die erwartete Kantenanzahl zwischen ihnen kleiner als die tatsächliche.
Der Modularity steigt daher zwangsweise durch deren Vernetzung.
Eine Konsequenz hieraus ist, dass der Greedyalgorithmus Communities mit weniger als $\sqrt{2m}$ internem Grad 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 z.B. mit dem Louvain Algorithmus relativiert werden.