Community Detection Flashcards
Das Community-Detection-Problem
„The problem of community detection requires the partition of a network into communities of densely connected nodes, with the nodes belonging to different communities being only sparsely connected.“ [Blondel et al., 2008]
Community Detection: Verschiedene Ansätze
- Verfahren zur Lösung des Community Detection Problems können in folgenden Gruppen zusammengefasst werden:
- Graphenpartitionierung
- Hierarchisches Clustering
- Partitionelles Clustering
- Spektrales Clustering
• Wir befassen uns in dieser Einheit mit Verfahren aus der Gruppe des Hierarchischen Clusterings.
Hierarchisches Clustering
„These techniques are aimed at discovering natural divisions of (social) networks into groups, based on various metrics of similarity or strength of connections between vertices.“ [Newman & Girvan, 2002]
- Verfahren dieser Kategorie werden dann angewendet, wenn keine sinnvolle Vorgabe für die Anzahl der Gruppen in einem Graphen getroffen werden kann.
- Sie identifizieren die Struktur der Gruppierungen innerhalb eines Graphen auf Basis der Relationen zwischen den Knoten.
- Dabei können auch verschachtelte Hierarchien von Gruppierungen erkannt werden.
- Es werden zwei unterschiedliche Verfahrenstypen unterschieden:
- Agglomerative (aufbauende) Algorithmen
- Divisive (abbauende) Algorithmen
Agglomerative Algorithmen
- Zunächst erfolgt die Berechnung einer paarweisen Distanz oder Ähnlichkeit zwischen allen Akteuren.
- Dann werden alle Verbindungen zwischen den Akteuren aus dem Netzwerk entfernt.
- Es folgt die schrittweise Ergänzung von Kanten zwischen den ähnlichsten Akteuren (Fusionierung).
- Die Fusionierungsphase stoppt bei einem Abbruchkriterium.
Divisive Algorithmen
- Zunächst erfolgt auch bei divisiven Verfahren die Berechnung einer paarweisen Distanz oder Ähnlichkeit zwischen allen Akteuren.
- Im Vergleich zu agglomerativen Verfahren werden jedoch schrittweise die Kanten zwischen den Akteuren mit der geringsten Ähnlichkeit entfernt.
- Das Verfahren stoppt, sobald ein Abbruchkriterium erreicht wurde.
Der Girvan-Newman-Algorithmus
- Der bekannteste divisive Algorithmus wurde von Girvan & Newman (2002, 2004) vorgestellt und später durch verschiedene Autoren weiterentwickelt.
- Der Grundgedanke des Verfahrens beruht auf der Entfernung der Kanten, die verschiedene Communities miteinander verbinden (→ Brücken).
- Girvan & Newman schlagen verschiedene Kennzahlen zur Identifikation derartiger Kanten vor.
- Die erfolgreichste Kennzahl ist die Edge Betweenness Centrality, eine Übertragung der für Knoten entwickelten Betweenness-Zentralität auf Kanten.
Der Girvan-Newman-Algorithmus (Schritte)
Der Girvan-Newman-Algorithmus lässt sich in folgende
Schritte einteilen:
1. Berechnung der Betweenness- Zentralität für alle Kanten im Netzwerk
2. Identifikation und Entfernung der Kante mit der höchsten Betweenness-Zentralität
3. Neuberechnung der Betweenness Zentralität für alle verbleibenden Kanten
4. Stopp, wenn es keine Kante mit einer Betweenness Zentralität größer c gibt
5. Gehe zu 2
Grundgedanke der Modularity
- Die Modularity ist eine Qualitätsfunktion, welche die Qualität der Partitionierung eines Graphen bewertet.
- Der grundlegende Gedanke ist, dass ein Zufallsgraph gleicher Größe keine Community-Struktur aufweisen, sondern alle Kanten eines Netzwerkes mit einer gleich hohen Wahrscheinlichkeit generieren würde.
- Der Zufallsgraph wird auch als Nullmodell bezeichnet und liefert eine Referenz, um die Dichte der Verbindungen innerhalb der Cluster einer Partitionierung zu bewerten.
- Ein gutes Nullmodell approximiert die Eigenschaften des tatsächlichen Netzwerkes (z.B. die Degree-Verteilung), ohne Community-Strukturen aufzuweisen.
Zufallsgraphen
“A random graph is simple to define. One takes some number N of nodes or „vertices“ and places connections or „edges“ between them, such that each pair of vertices i, j has a connecting edge with independent probability p. “[Newman et al., 2002]
- In Zufallsnetzwerken folgen die Knoten-Degrees der Poisson-Verteilung.
- Das heißt, ob eine Kante zwischen zwei Knoten existiert hängt ausschließlich von einem Poisson-Prozess ab.
- Die Wahrscheinlichkeitsfunktion der Poisson-Verteilung ist eine glockenförmige Kurve.
- Die meisten Knoten haben eine ähnliche Anzahl an Kanten. Knoten mit viel mehr oder viel weniger Verbindungen sind die Ausnahme.
- Alle Knoten sind in etwa gleich wichtig für den Zusammenhalt und den Ressourcenfluss im Netzwerk.
- Es hat sich die Bezeichnung „Zufallsnetzwerke“ für diese Netzwerke eingebürgert, der allerdings irreführend sein kann.
- Diese Struktur hat u.a. Auswirkungen auf Diffusionsprozesse im Netzwerk und die Auswirkungen von Knotenausfällen.
Degree-Verteilung in sozialen Netzwerken
- Der Degree eines Knotens entspricht der Anzahl seiner Nachbarn.
- In sozialen Netzwerken folgt der Degree in der Regel einer skalenfreien Verteilung.
- Man kann hier das „Power Law“ beobachten:
- Es gibt besonders viele Knoten mit einem niedrigen Degree.
- Es gibt besonders wenige Knoten mit einem hohen Degree.
- Der Degree der Akteure in sozialen Netzwerken ist häufig gemäß dem sogenannten Power Law verteilt:
- Es gibt besonders viele Akteure mit einem niedrigen Degree.
- Es gibt besonders wenige Akteure mit einem hohen Degree.
- Eine derartige Verteilung wird auch als scale-free („skalenfrei“) bezeichnet und folgt der Form 𝑃 (𝑑) = 𝑐d^(-y)
- Netzwerke dieser Art nennt man auch exponentiell, da die Wahrscheinlichkeit, dass ein Knoten mit genau k anderen Knoten verbunden ist, mit steigendem k exponentiell abnimmt.
Mathematische Formulierung der Modularity
- A ist die Adjazenzmatrix des Netzwerkes.
- m ist die gesamte Anzahl der Kanten.
- Pij ist die erwartete Anzahl der Kanten zwischen i und j im Nullmodell.
- 𝛿 (𝐶𝑖, 𝐶𝑗) ist genau dann 1, wenn i und j in der Partitionierung der gleichen Community zugeordnet sind, sonst 0.
Formel siehe Zusammenfassung
Modularity-maximierende Verfahren zur Community Detection
- Auf Basis der Modularity wurden weitere Verfahren entwickelt, die eine effiziente und effektive Identifikation guter Partitionierungen erlauben.
- Sie nutzen heuristische Optimierungsverfahren, um die Modularity einer initial generierten Partitionierung iterativ zu verbessern.
- Dabei erreichen sie oft lokal optimale Lösungen.
- Ein prominentes Beispiel ist der Algorithmus von Blondel et al. (2009), der im Folgenden zum Abschluss der Einheit vorgestellt wird.
Algorithmus: Blondel et al. (2009)
Phase 1
•Initialisierung: Teile die N Knoten des Netzwerkes je einer Gruppe zu
•Neuverteilung:
•Für jeden Knoten i
•Für alle Nachbarn j von i
•Berechne den Zuwachs der Modularity für den Fall, dass i der Gruppe von j zugewiesen wird
•Weise i der Gruppe mit dem maximalen Zuwachs der Modularity zu
•Wiederhole: bis ein lokales Optimum erreicht ist
Phase 2
•Knoten gleicher Gruppen werden zu einem Knoten zusammengefasst
•Beziehungen zwischen Knoten einer Gruppe werden als Kanten zwischen den Gruppenknoten modelliert
•Beziehungen zwischen Knoten einer Gruppe werden als Loop modelliert
•Kantengewichte entsprechen der Summe der Gewichte der aggregierten Kanten
Wiederholung
•Wiederhole Phasen 1 und 2, bis keine Verbesserung der Modularity mehr erreicht werden kann
